/
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 君は以下の操作により回文を作る.
- まず,S の断片を 1 つ選ぶ.選んだ断片を T とおく.
- 断片 T を昇順にソートしたものを T^{\prime} とおく.
- 数列 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}) とする.
- その後,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 であり,これが最長である.