题目描述
Taka 找到了一个长为 $N$ 的字符串, $S=(S_1,S_2...S_n)$ ,每个字符可以用 $1...C$ 之间的一个整数来表示。从这个字符串第 $i$ 个位置到第 $j$ 个位置的字符串 $S=(S_1,S_2...S_n)$称作字串 $(i,j)$ 。如果字串 $(i,j)$ 翻转后和原来相等,则称字串 $(i,j)$ 是回文的。Taka 进行如下操作来制作一个回文串:
- 首先,选择 $S$ 的一个子串。不妨设选择的子串为 $T$ .
- 将子串 按照升序排序,得到 $T'$ ;
- 在 $S$ 中,用 $T'$ 替换 $T$ ,得到 $S'$。形式化地:Taka 选择一个子串 $(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_{j+2}...S_N)$
- 在这之后,寻找 $S$ 中的最长的回文子串。
Taka 进行如上操作后,想要得到最长的回文子串。
现在 Taka 将字符串 $S$ 交给了你,请你输出 Taka 进行如上操作后能得到的最长回文子串的长度。
输入格式
第一行两个空格分隔的正整数 $N$ 和 $C$ ,分别表示字符串的长度和字符集大小; 接下来 $N$ 行,第 $i$ 行一个正整数 ,表示字符串 $S$ 中第 $i$ 个位置的字符。
输出格式
输出一行一个正整数,表示 Taka 进行操作后能得到的最长回文子串的长度。
样例 1
样例输入 1
12 26
26
17
17
17
1
26
1
17
19
20
1
14
样例输出 1
8
样例 2
样例输入 2
4 3
1
2
3
2
样例输出 2
3
数据范围与提示
对于全部数据,$1 \leq N,C \leq 3000$ , $1 \leq S_i \leq C $ 本题有四个子任务。只有该任务下测试点全部通过才能得到该子任务的分数。
Subtack | 附加限制 | 分数 |
---|---|---|
$1$ | $N,C \leq 50$ | 20 |
$2$ | $N,C \leq 300$ | 30 |
$3$ | $C \leq 2$ | 15 |
$4$ | $N,C \leq 3000$ | 35 |