题目描述
IOI2015 将要在哈萨克斯坦举行。哈萨克斯坦的「哈萨克」是用字母的 QAZAQ
拼写的。这个 QAZAQ
是回文。知晓这一点的 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 君进行如下操作来制作一个回文串:
- 首先,选择 S 的一个子串。不妨设选择的子串为 T;
- 将子串 T 按照升序排序,得到 T’;
- 在 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);
- 在这之后,寻找 S’ 中的回文子串。
JOI 进行如上操作后,想要得到最长的回文子串。
现在 JOI 君将字符串 S 交给了你,请你输出 JOI 君进行如上操作后能得到的最长回文子串的长度。
输入格式
第一行两个空格分隔的正整数 N 和 C,分别表示字符串的长度和字符集大小;
接下来 N 行,第 i 行一个正整数 Si,表示字符串 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
。
4 3
1
2
3
2
3
对于这组样例,S=(1,2,3,2),可以选择子串 (1,1) 进行排序,得到 S′=(1,2,3,2),子串 (2,4) 就是回文了。这个回文长度为 3,为最长可能得到的回文。
数据范围与提示
对于全部数据,1≤N,C≤3000,1≤Si≤C。
本题有两个子任务。只有该任务下测试点全部通过才能得到该子任务的分数。
Subtask |
附加限制 |
分数 |
1 |
N,C≤50 |
10 |
2 |
无附加限制 |
90 |