8248: BZOJ4248：AAQQZ

IOI2015将要在哈萨克斯坦举行。哈萨克斯坦的“哈萨克”是用字母的“QAZAQ”拼写的。这个“QAZQA”是回文— —知晓这一点的JOI君出于对回文的喜爱，准备用眼前的字符串制作一个回文。JOI君找到了一个长为N的字符串S=( S1,S2,...,SN)，每个字符可以用1...C之间的一个整数来表示。从这个字符串第i个位置到第j个位置的字符串(Si, Si+1,...,Sj)称作子串(i,j)。如果子串(i,j)翻转后和原来相等，即(Si,Si+1,...,Sj)=(Sj,Sj-1,...,Si)，则称 子串(i,j)是回文的。JOI君进行如下操作来制造回文： 1.        首先，选择S的一个子串。不妨设选择的子串为T。 2.        将子串T按照升序排序，得到T’ 3.        在S中，用T’替换T，得到S’。我们可以这样描述这三项操作：JOI君选择一个子串(i,j)，将Si,Si+1, ...,Sj按升序排序得到T’i,T’i+1,...,T’j，最终得到S’=(S1,S2,...,Si-1,T’i,T’i+1,...,T’j,Sj+1,...,SN) 4.        在这之后，寻找S’中的回文子串 JOI进行如上操作后，想要得到最长的回文子串 现在JOI君将字符串S交给了你，请你输出JOI君进行如上操作后能得到的最长回文子串的长度。

输入格式

第一行两个空格分隔的正整数N和C，分别表示字符串的长度和字符集大小 接下来N行，第i行一个正整数Si，表示字符串S中第i个位置的字符 1<=N<=3000 1<=C<=3000 1<=Si<=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