크기가 $N$인 정수 배열 $A$에 대하여, 셔플(shuffle) 연산은 다음과 같이 정의됩니다.

• 처음에 빈 정수 배열 $B$를 생성합니다.
• 그다음, $A$가 비어 있지 않은 동안 $A$의 가장 왼쪽 원소나 가장 오른쪽 원소 중 하나를 제거하고, 그 값을 $B$의 오른쪽에 추가합니다.
• $A$가 비어 있으면, $A$를 $B$로 교체하고 종료합니다.

위 그림과 같이 셔플 연산이 수행되면, 배열 $A$의 값은 다음과 같이 변경됩니다.

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

$A_i$를 배열 $A$의 $i$번째 원소라고 합시다. $1 \le i < j \le N$일 때 $A_i \le A_j$라는 조건이 성립하면, 배열 $A$가 단조 증가한다고 합니다.

크기가 $N$인 정수 배열 $A$가 주어졌을 때, 배열 $A$를 단조 증가하게 만드는 데 필요한 최소 셔플 연산 횟수를 계산하는 프로그램을 작성하세요.

입력

첫 번째 줄에는 배열 $A$의 원소 개수인 정수 $N$이 주어집니다 ($1 \le N \le 3 \cdot 10^5$). 두 번째 줄에는 배열 $A$의 초기 원소 값인 $N$개의 정수 $A_1, \dots, A_N$이 주어집니다 ($1 \le A_i \le 10^9$).

출력

배열 $A$를 단조 증가하게 만드는 데 필요한 최소 셔플 연산 횟수를 출력하세요.

예제

입력 1

3
2 2 5

출력 1

0

입력 2

6
1 5 8 10 3 2

출력 2

1