Minimum Operations to Achieve a Non-decreasing Sequence

You are given a sequence A of length \(n\). You are allowed to perform the following operation any number of times: choose any one element from the sequence and move it either to the beginning or the end of the sequence.

Your task is to determine the minimum number of operations required to transform the sequence into a non-decreasing sequence. A sequence is said to be non-decreasing if for every \(i\) (\(1 \le i < n\)), \(A_i \le A_{i+1}\).

Hint: Consider which elements do not need to be moved. In fact, if you can find the longest non-decreasing subsequence (LNDS) of the original sequence, then you only need to move the remaining elements. Therefore, the answer is \(n - L\), where \(L\) is the length of the longest non-decreasing subsequence.

The LNDS must be understood in the sense of not strictly increasing; equal elements are allowed.

Note: Any mathematical expressions should be formatted in \(\LaTeX\). For example, the condition is given by \(A_i \le A_{i+1}\) for \(1 \le i < n\) and the answer is \(n - L\) where \(L\) represents the length of the LNDS.

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)) representing the number of elements in the sequence.

The second line contains \(n\) space-separated integers \(A_1, A_2, \ldots, A_n\) representing the sequence.

outputFormat

Output a single integer representing the minimum number of operations needed to transform the sequence into a non-decreasing sequence.

sample

5
1 2 3 4 5

0