Bartek은 유명한 테크노 음악 프로듀서이며, 현재 다음 히트곡을 완성하는 중입니다. 그는 $1$부터 $n$까지 연속으로 번호가 매겨진 $n$개의 비트로 구성된 트랙을 만들었습니다. 음악 편집 프로그램에서 몇 시간을 보낸 후 mp3 파일을 내보내려던 참에, 현재 비트들이 $a_1, a_2, \dots, a_n$의 순서로 배열되어 있다는 것을 알아차렸습니다. Bartek은 비트들을 오름차순, 즉 $1, 2, \dots, n$의 순서로 만들어야 합니다.

프로그램에서는 두 가지 유형의 연산을 허용합니다:

• 마지막 비트를 원하는 위치로 이동합니다. 예: $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• 임의의 비트를 맨 앞으로 이동합니다. 예: $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

비트들을 오름차순으로 정렬하기 위해 필요한 최소 연산 횟수는 얼마입니까?

입력

첫 번째 줄에는 비트의 개수를 나타내는 정수 $n$ ($1 \le n \le 200\,000$)이 주어집니다.

두 번째 줄에는 프로그램에서 현재 비트의 순서를 나타내는, 쌍마다 서로 다른 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$)이 주어집니다.

출력

필요한 최소 연산 횟수를 나타내는 정수 하나를 출력합니다.

예제

입력 1

6
3 2 5 4 1 6

출력 1

4

입력 2

9
3 1 2 5 6 4 9 7 8

출력 2

6

노트

비트 수열 $(3, 2, 5, 4, 1, 6)$에서 시작합니다. 네 번의 연산으로 원하는 순서를 얻는 한 가지 방법은 다음과 같습니다:

• 마지막 비트를 왼쪽으로 두 칸 이동합니다: $(3, 2, 5, \underline{6}, 4, 1)$.
• 비트 $2$를 맨 앞으로 이동합니다: $(\underline{2}, 3, 5, 6, 4, 1)$.
• 비트 $1$을 맨 앞으로 이동합니다: $(\underline{1}, 2, 3, 5, 6, 4)$.
• 마지막 비트를 왼쪽으로 두 칸 이동합니다: $(1, 2, 3, \underline{4}, 5, 6)$.

네 번의 연산을 사용하여 다른 방법으로도 오름차순을 얻을 수 있지만, 세 번의 연산으로는 불가능하므로 결과는 $4$입니다.