순서 섞기

정수가 저장된 크기 $N$인 배열 $A$가 있을 때, "순서 섞기" 연산은 아래와 같이 정의된다.

1. 크기가 $N$인 배열 $B$를 이용하여, 배열 $A$의 좌측 끝 또는 우측 끝에 있는 값 중 하나를 차례로 꺼내어 배열 $B$에 좌측부터 순서대로 저장한다. 아래의 그림에서 값이 꺼내지는 순서는 9, 34, 19, 12, 25, 4, 5, 36이다.
2. 배열 $B$를 배열 $A$에 복사한다.

위에서 보인 그림처럼 순서 섞기 연산을 하면 배열 $A$의 값은 다음과 같이 변경된다.

$(34, 19, 5, 36, 4, 25, 12, 9) \Longrightarrow (9, 34, 19, 12, 25, 4, 5, 36)$

배열 $A$의 $i$번째 원소를 $A_i$라고 나타내자. "$1 \leq i \lt j \leq N$이면 $A_i ≤ A_j$이다."가 성립할 때, "배열 $A$는 단조증가한다"라고 말한다.

정수가 저장된 크기 $N$인 배열 $A$가 주어질 때, 배열 $A$가 단조증가하도록 정렬하기 위해 필요한 "순서 섞기" 연산의 최소 횟수를 계산하는 프로그램을 작성하시오.

제한사항

• $1 \leq N \leq 300,000$
• $1 \leq A_i \leq 10^9$

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

두 번째 줄에 배열 $A$에 저장된 $N$개의 정수 $A_1, \dots, A_N$이 공백을 사이에 두고 차례대로 주어진다.

배열 $A$가 단조증가하도록 정렬하기 위해 필요한 "순서 섞기" 연산의 최소 횟수를 출력한다.