시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB66272642.623%

문제

경기과학고등학교의 SRC(Science Research City) $8$층에는 $N$개의 실험실이 원형으로 배치되어 있다. 각 실험실은 $1$부터 $K$까지의 양의 정수 중 하나로 표현되는 실험을 수행하며, 같은 번호의 실험을 수행하는 실험실이 여러 곳 있을 수 있다. 시계 방향으로 $i$번째 ($1 \le i \le N$) 에 위치한 실험실이 수행하는 실험의 번호를 $A_i$라 하자.

올해 SRC에는 $1$층에서 $8$층으로 바로 이동할 수 있는 무중력 발사대가 새로 설치된다. 무중력 발사대는 원형으로 배치된 실험실 중 하나에 설치되며, 학생들은 발사대에서 내린 후 그 실험실을 시작으로 시계 방향으로 한 바퀴를 돌면서 $N$개의 실험실을 차례대로 지나게 된다. 이때, $i$번째 실험실에서 내린 뒤 방문한 순서대로 실험실의 실험 번호를 나열한 수열을 $P_i$라 하자. 즉, $P_i = [A_i, A_{i+1}, \cdots, A_N, A_1, A_2, \cdots, A_{i-1}]$이다.

무중력 발사대를 설치할 실험실을 정하기 위해, 여러분은 모든 실험실에 등급을 매길 것이다. 등급은 실험실을 순서대로 지나면서 얼마나 다양한 실험을 수행할 수 있는지에 따라 결정된다. 길이가 $L$이고 $1$ 이상 $K$ 이하의 정수로 이루어진 수열은 모두 $K^L$가지가 있다. 이 $K^L$가지 수열이 모두 $P_i$의 부분 수열로 존재하면 $i$번 실험실이 등급 $L$을 만족한다고 한다. $i$번 실험실의 등급은 $i$번 실험실이 만족하는 등급 $L$의 최댓값으로 정의되며, 만약 그러한 양의 정수 $L$이 존재하지 않는다면 $i$번 실험실의 등급은 $0$이다.

이때, $N$개 실험실의 등급의 최댓값을 구하여라.

부분 수열의 정의는 하단의 노트를 참고하라.

입력

첫 번째 줄에 $N, K$가 공백으로 구분되어 주어진다.

두 번째 줄에 수열 $A$의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 문제의 정답을 출력하라.

제한

  • $1 \le K \le N \le 10^6$
  • $1 \le A_i \le K \ (1 \le i \le N)$

서브태스크

번호배점제한
14

$K = N$

217

등급이 최대인 위치 중 하나가 $A_N$과 $A_1$ 사이임을 보장한다.

314

$N \le 5 \, 000; \ K \le 2$

421

$N \le 5 \, 000$

544

추가 제한 조건 없음

예제 입력 1

4 2
1 2 2 1

예제 출력 1

2

첫 번째 입력에서는 $1$번 실험실에 무중력 발사대를 설치했을 때, $P_1 = [1, 2, 2, 1]$ 이다. $P_1$에서 부분 수열로 길이 $2$의 수열 $[1, 1], [1, 2], [2, 1], [2, 2]$를 모두 찾을 수 있고, 길이 $3$의 수열 $[2, 1, 1]$ 등을 찾을 수 없기 때문에, 등급이 $2$이다. 이 실험실에서의 등급이 최대임을 보일 수 있다.

예제 입력 2

10 3
1 2 3 3 1 3 2 2 3 1

예제 출력 2

3

노트

수열 $P$의 부분 수열이란, 수열 $P$에서 $0$개 이상의 원소를 제거해서 만든 수열을 뜻한다.

$P = [1, 2, 4, 1]$ 에서 부분 수열의 예시로는 $[1, 4, 1], [2, 4]$ 등이 있다. 부분 수열이 아닌 예시로는 $[2, 1, 1]$ 등이 있다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.