문제
길이 \(N\)인 수열 \(A = [A_1, A_2, \ldots, A_N]\)이 주어진다. 다음 연산을 0번 이상 수행할 수 있다.
수열 \(A\)를 비내림차순(\(A_1 \le A_2 \le \cdots \le A_N\))으로 정렬하는 데 필요한 연산 횟수의 최솟값을 구하는 프로그램을 작성하라. 제약 조건을 만족하는 모든 입력에 대해, 주어진 연산만으로 수열을 정렬할 수 있음이 보장된다. |
입력
입력은 다음 형식으로 주어진다.
\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
제약 조건
- 주어지는 모든 수는 정수이다.
- \(1 \le N \le 300{,}000\)
- \(1 \le A_i \le N\) (\(1 \le i \le N\))
부분문제
- (6점) \(A_i \le 2\) (\(1 \le i \le N\))
- (15점) \(N \le 15\)
- (23점) \(N \le 100\)
- (27점) \(N \le 750\)
- (33점) \(A_i \ne A_j\) (\(1 \le i < j \le N\))
- (46점) 추가 제약 조건 없음
출력
다음 형식으로 출력한다.
수열 \(A\)를 비내림차순으로 정렬하는 데 필요한 연산 횟수의 최솟값을 출력한다.
예시 1
입력
6
3 4 5 1 2 6
출력
1
설명
\(x = 2\)를 고르면 부분수열 \(B = [1, 2]\), \(C = [3, 4, 5, 6]\)이 되어 \(A = [1, 2, 3, 4, 5, 6]\)으로 정렬된다. 따라서 1번의 연산으로 정렬할 수 있다.
예시 2
입력
9
1 5 9 9 5 1 1 5 9
출력
2
설명
다음과 같이 2번의 연산으로 정렬할 수 있다.
- \(x = 3\)을 고르면 \(B = [1, 1, 1]\), \(C = [5, 9, 9, 5, 5, 9]\)이 되어 \(A = [1, 1, 1, 5, 9, 9, 5, 5, 9]\)가 된다.
- \(x = 7\)을 고르면 \(B = [1, 1, 1, 5, 5, 5]\), \(C = [9, 9, 9]\)이 되어 \(A = [1, 1, 1, 5, 5, 5, 9, 9, 9]\)가 된다.
1번 이하의 연산으로는 정렬할 수 없음을 증명할 수 있다.