Book Sorting

시간 제한2초메모리 제한2048 MB

요약

책 n권의 순열이 주어질 때, 인접한 두 책을 맞바꾸거나 한 책을 맨 왼쪽 또는 맨 오른쪽으로 옮기는 연산만으로 오름차순으로 정렬하는 최소 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

You have $n$ books arranged from left to right on a bookshelf. These books are uniquely labeled from $1$ to $n$ . The $i$ -th book from the left is labeled $p\_i$ . You want to sort the books so that their labels are in ascending order from left to right.

In one step, you can perform one of the following actions:

Choose two adjacent books and swap them.
Choose one book and move it to the leftmost position.
Choose one book and move it to the rightmost position.

Compute the minimum number of steps required to sort the books.

입력

The first line of input contains an integer $n$ ( $2 ≤ n ≤ 500\\, 000$ ). The second line contains $n$ pairwise distinct integers $p\_1, p\_2, \dots , p\_n$ ( $1 ≤ p\_i ≤ n$ ).

출력

Output the minimum number of steps to sort the books in ascending order from left to right by their labels.

예제2

예제 1
입력
```
6
6 2 1 4 3 5
```
예상 출력
```
3
```
예제 2
입력
```
9
9 2 4 3 7 5 1 8 6
```
예상 출력
```
5
```