Minimum Removals for Increasing Sequence

Given a sequence of integers, determine the minimum number of elements that must be removed so that the remaining sequence is strictly increasing.

Let \(n\) be the number of elements in the sequence and \(L\) be the length of its longest strictly increasing subsequence (LIS). The answer is given by \(n - L\).

Example: For the sequence [3, 7, 5, 2, 6, 4, 9] with \(n = 7\), the longest strictly increasing subsequence is [3, 5, 6, 9] (or another of the same length) so \(L = 4\), and the minimum number of removals is \(7 - 4 = 3\>.

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains a single integer \(n\) representing the number of elements in the sequence.
• The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

Output a single integer to stdout — the minimum number of removals required so that the remaining sequence is strictly increasing.

## sample

7
3 7 5 2 6 4 9

3

</p>