SRC 무중력 발사대

경기과학고등학교의 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 \leq K \leq N \leq 1 \ 000 \ 000$ $1 \leq A_i \leq N$