#3001. 「JOISC 2015 Day 3」AAQQZ

---

题目描述

译自 JOISC 2015 Day3 T1「AAQQZ」，感谢 PoPoQQQ 提供翻译。

IOI2015 将要在哈萨克斯坦举行。哈萨克斯坦的「哈萨克」是用字母的 QAZAQ 拼写的。这个 QAZAQ 是回文。知晓这一点的 JOI 君出于对回文的喜爱，准备用眼前的字符串制作一个回文串。

JOI 君找到了一个长为 $N$ 的字符串 $S=(S_1,S_2,\cdots ,S_N)$，每个字符可以用 $1\ldots C$ 之间的一个整数来表示。从这个字符串第 $i$ 个位置到第 $j$ 个位置的字符串 $(S_i,S_{i+1},\cdots ,S_j)$ 称作子串 $(i,j)$。如果子串 $(i,j)$ 翻转后和原来相等，即 $(S_i,S_{i+1},\cdots ,S_j)=(S_j,S_{j-1},\cdots ,S_i)$，则称子串 $(i,j)$ 是回文的。JOI 君进行如下操作来制作一个回文串：

1. 首先，选择 $S$ 的一个子串。不妨设选择的子串为 $T$；
2. 将子串 $T$ 按照升序排序，得到 $T'$；
3. 在 $S$ 中，用 $T'$ 替换 $T$，得到 $S'$。我们可以这样描述这三项操作：JOI 君选择一个子串 $(i,j)$，将 $S_i,S_{i+1},\cdots ,S_j$ 按升序排序得到 $T'_i,T'_{i+1},\cdots ,T'_j$，最终得到 $S'=(S_1,S_2,\cdots ,S_{i-1},T'_i,T'_{i+1},\cdots ,T'_j,S_{j+1},\cdots ,S_N)$；
4. 在这之后，寻找 $S'$ 中的回文子串。

JOI 进行如上操作后，想要得到最长的回文子串。

现在 JOI 君将字符串 $S$ 交给了你，请你输出 JOI 君进行如上操作后能得到的最长回文子串的长度。

---

输入格式

第一行两个空格分隔的正整数 $N$ 和 $C$，分别表示字符串的长度和字符集大小；

接下来 $N$ 行，第 $i$ 行一个正整数 $S_i$，表示字符串 $S$ 中第 $i$ 个位置的字符。

---

输出格式

输出一行一个正整数，表示 JOI 君进行操作后能得到的最长回文子串的长度。

---

样例 1

输入

12 26
26
17
17
17
1
26
1
17
19
20
1
14

输出

8

解释
样例输入中，$N=12$，$C=26$，$S=(26,17,17,17,1,26,1,17,19,20,1,14)$。JOI 君可以选择子串 $(4,8)$，将其按照升序排列，得到 $S'=(26,17,17,1,1,17,17,26,19,20,1,14)$，这样子串 $(1,8)$ 就是回文了。这个回文长度为 $8$，是最长可能得到的回文子串。

若转化为字母序列，则原串为 ZQQQAZAQSTAN。

---

样例 2

输入

4 3
1
2
3
2

输出

3

对于这组样例，$S=(1,2,3,2)$，可以选择子串 $(1,1)$ 进行排序，得到 $S'=(1,2,3,2)$，子串 $(2,4)$ 就是回文了。这个回文长度为 $3$，为最长可能得到的回文。

---

数据范围与提示

对于全部数据，$1\le N,C\le 3000$，$1\le S_i\le C$。

本题有两个子任务。只有该任务下测试点全部通过才能得到该子任务的分数。

Subtask	附加限制	分数
1	$N,C\le 50$	$10$
2	无附加限制	$90$