시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB86571.429%

문제

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

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

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

  1. まず,S の断片を 1 つ選ぶ.選んだ断片を T とおく.
  2. 断片 T を昇順にソートしたものを T ′ とおく.
  3. 数列 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) とする.
  4. その後,S′ の断片で回文になっているものを探す.

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

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

입력

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

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

출력

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

제한

  • 1 ≦ N ≦ 3 000.
  • 1 ≦ C ≦ 3 000.
  • 1 ≦ Si ≦ C (1 ≦ i ≦ N).

서브태스크 1 (10점)

  • N ≦ 50.
  • C ≦ 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′ = (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′ = (1, 2, 3, 2) となる.S と S′ は同じ数列である.S′ の断片 (2, 4) が回文になる.この回文の長さは 3 であり,これが最 長である.

채점 및 기타 정보

  • 예제는 채점하지 않는다.