Book Sorting

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.