P3411 Sequence Transformation

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.

The first line contains a positive integer $n$. The second line contains $n$ positive integers $A_i$.

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

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