Lining Up in Order

There are $N$ children standing in a single line in a playground. Each child wears a distinct number from $1$ to $N$ (that is, the numbers form a permutation of $1$ through $N$). A teacher wants to rearrange the children into increasing order of their numbers — $1, 2, \dots, N$ — using only the following operation.

Operation: choose one child in the line and send that child to either the very front or the very back of the line.

When a child leaves a spot, the gap is closed: every child behind the gap steps forward by one position to fill it.

For example, suppose $5$ children stand in this order:

5 2 4 1 3

They can be sorted with three operations:

1. Send child $1$ to the front. (5 2 4 1 3 → 1 5 2 4 3)
2. Send child $4$ to the back. (1 5 2 4 3 → 1 5 2 3 4)
3. Send child $5$ to the back. (1 5 2 3 4 → 1 2 3 4 5)

No sequence of two or fewer operations can sort this arrangement, so the minimum number of moves here is $3$.

Given the initial arrangement, find the minimum number of children that must be sent to the front or the back in order to line everyone up in increasing order of their numbers.

The input consists of two lines. The first line contains an integer $N$, the number of children. The second line contains the children's numbers in the order they are standing, separated by single spaces. It is guaranteed that $1 \le N \le 1{,}000{,}000$ and that the numbers form a permutation of the integers from $1$ to $N$.

Print, on a single line, the minimum number of children that must be sent to the front or the back to arrange them in increasing order of their numbers.