题目描述

IOI2015将要在哈萨克斯坦举行。哈萨克斯坦的“哈萨克”是用字母的“QAZAQ”拼写的。这个“QAZQA”是回文— —知晓这一点的JOI君出于对回文的喜爱，准备用眼前的字符串制作一个回文。JOI君找到了一个长为$N$的字符串$S=(S_1,S_2,...,S_N)$，每个字符可以用$1...C$之间的一个整数来表示。从这个字符串第$i$个位置到第$j$个位置的字符串$(S_i,S_{i+1},...,S_j)$称作子串$(i,j)$。如果子串$(i,j)$翻转后和原来相等，即$(S_i,S_{i+1},...,S_j)=(S_j,S_{j-1},...,S_i)$，则称子串$(i,j)$是回文的。JOI君进行如下操作来制造回文：

1. 首先，选择$S$的一个子串。不妨设选择的子串为$T$。
2. 将子串$T$按照升序排序，得到$T'$
3. 在$S$中，用$T'$替换$T$，得到$S'$. 我们可以这样描述这三项操作：JOI君选择一个子串$(i,j)$，将$S_i,S_{i+1},...,S_j$按升序排序得到$T'_i,T'_{i+1},...,T'_j$，最终得到$S'=(S_1,S_2,...,S_{i-1},T'_i,T'_{i+1},...,T'_j,S_{j+1},...,S_N)$
4. 在这之后，寻找$S'$中的回文子串 JOI进行如上操作后，想要得到最长的回文子串。现在JOI君将字符串$S$交给了你，请你输出JOI君进行如上操作后能得到的最长回文子串的长度。

给定一个字符串, 可以对这个字符串的一个区间排序, 求允许排序一次的最长回文子串。

输入格式

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

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

$1 \leq N \leq 3000$

$1 \leq C \leq 3000$

$1 \leq S_i \leq C$

输出格式

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

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，是最长可能得到的回文子串。

题目来源

JOI 2014~2015 春季training合宿 竞技3 By PoPoQQQ