스택정렬

문제

스택(Stack) 안에 $N$개의 원소가 쌓여있다. 스택의 바닥(왼쪽)은 막혀있고 상단(오른쪽)은 뚫려있다. 따라서 다음과 같은 연산만 수행할 수 있다.

• pop: 스택의 상단에 있는 원소 하나를 빼낸다. 빼낸 원소는 임시 공간에 보관한다. 스택이 비었을 때는 pop을 할 수 없다.

• push: 임시 공간에 보관 중인 원소 중 하나를 선택하여 스택의 탑에 집어넣는다. 임시 공간에 원소가 없으면 push를 할 수 없다.

진원이는 이 스택 내부에 있는 원소들을 pop과 push만을 이용하여 비내림차순으로 정렬하고 싶다. 즉, 스택의 바닥 원소가 가장 작아야 하고, 상단으로 갈 수록 같거나 증가하며 상단 원소가 가장 커야 한다.

진원이는 바쁜 몸이기 때문에 스택에서 원소들을 최대한 덜 pop하고 싶어한다. pop 연산의 최소 횟수를 구하는 프로그램을 작성해 보자.

입력

첫째 줄에 스택 내의 원소의 개수 $N$이 주어진다. ($1 \le N \le 1,000,000$)

둘째 줄에 스택에 들어있는 $N$개의 원소들이 스택의 바닥부터 상단까지 순서대로 공백으로 구분되어 주어진다. 각 원소들은 $1$ 이상 $10^9$ 이하의 정수다.

출력

스택을 비내림차순으로 정렬하기 위해 필요한 pop 횟수의 최솟값을 출력한다.

예제 입력 1

5
1 2 4 3 5

예제 출력 1

3

예제 입력 2

4
4 3 2 1

예제 출력 2

4