Description

Given a sequence $A_i$ of length $n$.

You may perform several operations. In each operation, you can choose any number in the sequence and move it to the beginning or to the end of the sequence.

Find the minimum number of operations needed to make the sequence non-decreasing. "Non-decreasing" means that every number in the sequence is not greater than the number that follows it.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $A_i$.

Output Format

Output a single integer, representing the minimum number of operations required.

5
6 3 7 8 6

2

Hint

For $30 \%$ of the testdata, $1 \le n \le 10$.

For $60 \%$ of the testdata, $1 \le n \le 1000$.

For $100 \%$ of the testdata, $1 \le n \le {10}^6$, $1 \le A_i \le {10}^6$.

Translated by ChatGPT 5