Skip to content
Sign in

수열 정렬하기

Unrated
한국어

Language

Contribute a translation
Time limit
1000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

길이가 $N$인 수열 $A = \left[ A_1, A_2, \cdots, A_N \right]$이 주어진다. 여러분은 다음과 같은 시행을 $0$번 이상 자유롭게 할 수 있다.

  1. 양의 정수 $x$를 정한다.
  2. 수열 $A$의 원소 중 값이 $x$ 이하인 원소들을 원래 순서대로 추출하여 부분 수열 $B$를 만든다.
  3. 수열 $A$의 원소 중 값이 $x$ 초과인 원소들을 원래 순서대로 추출하여 부분 수열 $C$를 만든다.
  4. 기존 수열 $A$를, $B$와 $C$를 순서대로 이어 붙인 수열($B + C$)로 대체한다.

수열 $A$를 비내림차순($A_1 \le A_2 \le \cdots \le A_N$)으로 정렬하기 위해서 최소 몇 번의 시행이 필요한지 계산하는 프로그램을 작성하라.

제약 조건을 만족하는 모든 입력에 대해, 주어진 시행을 통해 수열을 비내림차순으로 정렬하는 방법이 존재함을 증명할 수 있다.

Constraints

  • 주어지는 모든 수는 정수이다.
  • $1 \le N \le 300\,000$
  • 정수 $i$ ($1 \le i \le N$)에 대하여 $1 \le A_i \le N$

Subtasks

  1. (6점) 정수 $i$ ($1 \le i \le N$)에 대하여 $A_i \le 2$
  2. (15점) $N \le 15$
  3. (23점) $N \le 100$
  4. (27점) $N \le 750$
  5. (33점) 정수 $i$, $j$ ($1 \le i < j \le N$)에 대하여 $A_i \neq A_j$
  6. (46점) 추가 제약 조건 없음.

Input

첫 줄에 정수 $N$이 주어진다.

그다음 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 차례대로 주어진다.

Output

첫 줄에 수열 $A$를 비내림차순으로 정렬하기 위해 필요한 최소 시행 횟수를 출력한다.

Examples

Sample input 1
6
3 4 5 1 2 6
Sample output 1
1

다음과 같이 $1$번의 시행으로 수열 $A$를 비내림차순으로 정렬할 수 있다.

  1. $x = 2$로 정하자.

    • 값이 $x = 2$ 이하인 원소들을 원래 순서대로 추출하면 $B := [1, 2]$.

      • 값이 $x = 2$ 초과인 원소들을 원래 순서대로 추출하면 $C := [3, 4, 5, 6]$.
      • 따라서, 수열 $A$는 $B + C = [1, 2, 3, 4, 5, 6]$로 대체된다.
Sample input 2
9
1 5 9 9 5 1 1 5 9
Sample output 2
2

다음과 같이 $2$번의 시행으로 수열 $A$를 비내림차순으로 정렬할 수 있다.

  1. $x = 3$으로 정하자.

    • 값이 $x = 3$ 이하인 원소들을 원래 순서대로 추출하면 $B := [1, 1, 1]$.

      • 값이 $x = 3$ 초과인 원소들을 원래 순서대로 추출하면 $C := [5, 9, 9, 5, 5, 9]$.
      • 따라서, 수열 $A$는 $B + C = [1, 1, 1, 5, 9, 9, 5, 5, 9]$로 대체된다.

  2. $x = 7$로 정하자.

    • 값이 $x = 7$ 이하인 원소들을 원래 순서대로 추출하면 $B := [1, 1, 1, 5, 5, 5]$.

      • 값이 $x = 7$ 초과인 원소들을 원래 순서대로 추출하면 $C := [9, 9, 9]$.
      • 따라서, 수열 $A$는 $B + C = [1, 1, 1, 5, 5, 5, 9, 9, 9]$로 대체된다.

$2$번보다 적은 횟수의 시행으로는 수열 $A$를 비내림차순으로 정렬하는 것이 불가능함을 증명할 수 있다.

Tags

No tags yet

Source