시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB141111100.000%

문제

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.

예제 입력 1

6
6 2 1 4 3 5

예제 출력 1

3

You can do the following three steps in order: swap the books labeled $2$ and $1$, swap the books labeled $4$ and $3$, and move the book labeled $6$ to the rightmost position.

6 2 1 4 3 5 → 6 1 2 4 3 5 → 6 1 2 3 4 5 → 1 2 3 4 5 6

It can be shown that two or fewer steps are insufficient to sort the books.

예제 입력 2

9
9 2 4 3 7 5 1 8 6

예제 출력 2

5