Minimum Trees to Cut

You are given n, the number of trees, and a sequence of n integers representing the heights of the trees. Your task is to remove (cut) the minimum number of trees so that the remaining trees form a strictly increasing sequence.

Let \(L\) be the length of the longest increasing subsequence among the tree heights. Then the answer is \(n - L\).

For example, if you have 5 trees with heights [3, 7, 5, 6, 9], the longest increasing subsequence is [3, 5, 6, 9] with a length of 4, so only 1 tree needs to be cut. Your program should read from standard input and output the result to standard output.

inputFormat

The input contains two lines:

• The first line contains an integer \(n\) representing the number of trees.
• The second line contains \(n\) space-separated integers representing the heights of the trees.

All input is read from standard input.

outputFormat

Output a single integer representing the minimum number of trees to cut so that the remaining trees form a strictly increasing sequence. The output should be written to standard output.

## sample

5
3 7 5 6 9

1

</p>