경기과학고등학교의 SRC(Science Research City) 층에는 개의 실험실이 원형으로 배치되어 있다. 각 실험실은 부터 까지의 양의 정수 중 하나로 표현되는 실험을 수행하며, 같은 번호의 실험을 수행하는 실험실이 여러 곳 있을 수 있다. 시계 방향으로 번째 () 에 위치한 실험실이 수행하는 실험의 번호를 라 하자.
올해 SRC에는 층에서 층으로 바로 이동할 수 있는 무중력 발사대가 새로 설치된다. 무중력 발사대는 원형으로 배치된 실험실 중 하나에 설치되며, 학생들은 발사대에서 내린 후 그 실험실을 시작으로 시계 방향으로 한 바퀴를 돌면서 개의 실험실을 차례대로 지나게 된다. 이때, 번째 실험실에서 내린 뒤 방문한 순서대로 실험실의 실험 번호를 나열한 수열을 라 하자. 즉, 이다.
무중력 발사대를 설치할 실험실을 정하기 위해, 여러분은 모든 실험실에 등급을 매길 것이다. 등급은 실험실을 순서대로 지나면서 얼마나 다양한 실험을 수행할 수 있는지에 따라 결정된다. 길이가 이고 이상 이하의 정수로 이루어진 수열은 모두 가지가 있다. 이 가지 수열이 모두 의 부분 수열로 존재하면 번 실험실이 등급 을 만족한다고 한다. 번 실험실의 등급은 번 실험실이 만족하는 등급 의 최댓값으로 정의되며, 만약 그러한 양의 정수 이 존재하지 않는다면 번 실험실의 등급은 이다.
이때, 개 실험실의 등급의 최댓값을 구하여라.
부분 수열의 정의는 하단의 노트를 참고하라.
첫 번째 줄에 가 공백으로 구분되어 주어진다.
두 번째 줄에 수열 의 원소 이 공백으로 구분되어 주어진다.
첫 번째 줄에 문제의 정답을 출력하라.
첫 번째 입력에서는 번 실험실에 무중력 발사대를 설치했을 때, 이다. 에서 부분 수열로 길이 의 수열 를 모두 찾을 수 있고, 길이 의 수열 등을 찾을 수 없기 때문에, 등급이 이다. 이 실험실에서의 등급이 최대임을 보일 수 있다.
| 4 | 25 |
| 5 | 29 | 추가 제약 조건 없음 |
