Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB

#2191. kanzenkankaku

统计

题目描述

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 进行如下操作来制作一个回文串:

  1. 首先,选择 $S$ 的一个子串。不妨设选择的子串为 $T$ .
  2. 将子串 按照升序排序,得到 $T'$ ;
  3. 在 $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)$
  4. 在这之后,寻找 $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