H - AAQQZ Editorial /

Time Limit: 4 sec / Memory Limit: 256 MiB

配点 : 100 点

問題文

2015 年の国際情報オリンピックはカザフスタンで行われる.カザフスタンの「カザフ」は,アルファベットで “QAZAQ” と綴られることがある.この QAZAQ は回文である.このことを知った JOI 君は,回文が好きになって,目についた文字列から回文を作ることにした.

JOI 君が見つけたのは長さが N の文字列である.各文字には 1 から C までの整数が定まっており,文字列の文字を整数に置き換えた数列を S = (S_{1}, S_{2}, \ldots, S_{N}) とする.この数列の i 番目から j 番目まで (1 \leqq i \leqq j \leqq N) を取り出した数列 (S_{i}, S_{i+1}, \ldots, S_{j}) を断片 (i, j) と呼ぶ.断片 (i, j) がそれを逆転させた数列と等しいとき,すなわち,(S_{i}, S_{i+1}, \ldots, S_{j}) = (S_{j}, S_{j - 1}, \ldots, S_{i}) が成り立つとき,断片 (i, j) は回文である.

JOI 君は以下の操作により回文を作る.

  1. まず,S の断片を 1 つ選ぶ.選んだ断片を T とおく.
  2. 断片 T を昇順にソートしたものを T^{\prime} とおく.
  3. 数列 S に対し,断片 T を T^{\prime} に置き換える.置き換えたものを S^{\prime} とする.すなわち,JOI 君が断片 (i, j) を選んだとき,S_{i}, S_{i+1}, \ldots, S_{j} を昇順にソートしたものを T_{i}^{\prime} \leqq T_{i+1}^{\prime} \leqq \cdots \leqq T_{j}^{\prime} として,S^{\prime} = (S_{1}, S_{2}, \ldots, S_{i - 1}, T_{i}^{\prime}, T_{i+1}^{\prime}, \ldots, T_{j}^{\prime}, S_{j+1}, \ldots, S_{N}) とする.
  4. その後,S^{\prime} の断片で回文になっているものを探す.

JOI 君はこの操作により,できるだけ長い回文を作りたい.

課題

JOI 君の見つけた文字列を表す数列 S が与えられる.JOI 君が作ることができる回文の長さの最大値を求めよ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には,整数 N,C が空白を区切りとして書かれている.N は JOI 君の見つけた文字列の長さを表す.C は文字に定められた整数の上限を表す.
  • 続く N 行には,JOI 君の見つけた文字列を表す数列 S の情報が書かれている.これらの行のうちの i 行目 (1 \leqq i \leqq N) には整数 S_{i} が書かれている.S_{i} は数列 S の i 番目の整数を表す.

出力

標準出力に,JOI 君が作ることができる回文の長さの最大値を表す整数を 1 行で出力せよ.

制約

すべての入力データは以下の条件を満たす.

  • 1 \leqq N \leqq 3\,000.
  • 1 \leqq C \leqq 3\,000.
  • 1 \leqq S_{i} \leqq C (1 \leqq i \leqq N).

小課題

小課題 1 [10 点]

以下の条件を満たす.

  • N \leqq 50.
  • C \leqq 50.

小課題 2 [90 点]

追加の制限はない.

入力例 1

12 26
26
17
17
17
1
26
1
17
19
20
1
14

出力例 1

8

この入力例では,N = 12,C = 26 で,S = (26, 17, 17, 17, 1, 26, 1, 17, 19, 20, 1, 14) である.ここで,断片 (4, 8) を昇順にソートすることで S^{\prime} = (26, 17, 17, 1, 1, 17, 17, 26, 19, 20, 1, 14) となり,断片 (1, 8) が回文になる.この回文の長さは 8 であり,これが最長である.

入力例 2

4 3
1
2
3
2

出力例 2

3

この入力例では,S = (1, 2, 3, 2) である.ここで,断片 (1, 1) を昇順にソートすることで,S^{\prime} = (1, 2, 3, 2) となる.S と S^{\prime} は同じ数列である.S^{\prime} の断片 (2, 4) が回文になる.この回文の長さは 3 であり,これが最長である.


Source Name

JOI 2014/2015 春季トレーニング合宿 Contest Day3