AAQQZ
시간 제한2초메모리 제한512 MB
수열의 연속한 한 구간을 오름차순으로 정렬한 뒤 얻을 수 있는 가장 긴 회문 부분 수열의 길이를 구한다.
문제
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 君は以下の操作により回文を作る．
- まず，S の断片を 1 つ選ぶ．選んだ断片を T とおく．
- 断片 T を昇順にソートしたものを T ′ とおく．
- 数列 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) とする．
- その後，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)．