나연 정렬

자료구조 수업을 열심히 들은 나연이는 새로운 정렬 알고리즘을 고안하고 자신의 이름을 따 나연 정렬이라고 이름 붙였다. 정렬할 배열 $A=[a_1,a_2,\cdots,a_N]$이 주어지면 나연 정렬은 다음과 같이 동작한다.

1. 빈 스택을 원하는 만큼 선언한다.
2. $a_1$부터 $a_N$까지 각 원소를 순서대로 원하는 스택에 삽입한다.
3. 빈 배열 $B$를 선언한다.
4. 모든 스택이 빌 때까지, 원하는 스택에서 원소를 하나 뽑아 $B$의 맨 뒤에 삽입하는 작업을 반복한다.

나연 정렬로 배열을 정렬할 수 있는지는 배열과 사용하는 스택의 개수에 따라 달라진다. 예를 들어 $A=[9,2,8,7,1]$이라면 3개의 스택에 각각 $[9,8]$, $[2]$, $[7,1]$을 담고, 세 번째, 두 번째, 세 번째, 첫 번째, 첫 번째 스택 순서로 원소를 뽑으면 오름차순으로 정렬된 배열을 얻는다. 스택이 두 개여도 $A$를 정렬할 수 있지만, 스택이 하나뿐이면 오름차순으로 정렬할 수 없다.

나연이는 주어진 배열을 오름차순으로 정렬하는 데 필요한 스택의 최소 개수를 구해 주면 HCPC에서 푼 문제 수를 몰래 하나 늘려 주겠다고 제안했다. 누구보다 먼저 문제를 풀고 HCPC 우승에 한 걸음 다가가 보자.

첫째 줄에 배열 $A$의 길이를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 500,000$)

둘째 줄에 $N$개의 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 10^9$)

첫째 줄에 $A$를 오름차순으로 정렬하는 데 필요한 최소 스택 개수를 출력한다.