Description

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.

Input Format

The first line of input contains an integer $n$ ($2 \leq n \leq 500\,000$). The second line contains $n$ pairwise distinct integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$).

Output Format

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

6
6 2 1 4 3 5

3

9
9 2 4 3 7 5 1 8 6

5

Hint

Explanation for the sample input/output #1

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.

$\begin{aligned}6 \ 2 \ 1 \ 4 \ 3 \ 5 &\rightarrow 6 \ \mathbf{1} \ \mathbf{2} \ 4 \ 3 \ 5 \\&\rightarrow 6 \ 1 \ 2 \ \mathbf{3} \ \mathbf{4} \ 5 \\&\rightarrow 1 \ 2 \ 3 \ 4 \ 5 \ \mathbf{6}\end{aligned}$

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