32873번 - 나연 정렬

문제

자료구조 수업을 열심히 수강한 나연이는 새로운 정렬 알고리즘을 고안한 뒤, 자신의 이름을 따 나연 정렬이라는 이름을 붙였다. 정렬하고자 하는 배열 $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$를 오름차순으로 정렬하기 위해 필요한 최소 스택 개수를 출력한다.

제한

힌트