Minimum Cuts to Achieve a Strictly Increasing Sequence

You are given a sequence of N integers representing the heights of trees in a row. Your task is to determine the minimum number of cuts (removals) required so that the remaining trees have strictly increasing heights.

This problem can be solved by finding the Longest Increasing Subsequence (LIS) of the given sequence. Let \(dp\) denote the length of the LIS. Then, the minimum number of cuts needed is:

$$\text{cuts} = N - \max(dp)$$

For example, if the sequence is [3, 4, 2, 5, 7] with \(N=5\), the longest increasing subsequence is [3, 4, 5, 7] (length 4), so the answer is \(5 - 4 = 1\).

Note: The input will be provided via standard input (stdin) and the result should be printed to standard output (stdout).

inputFormat

The input consists of two lines:

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

All input values are provided via standard input.

outputFormat

Output a single integer representing the minimum number of cuts (removals) required to achieve a strictly increasing sequence of tree heights. The result should be printed to standard output.

## sample

5
3 4 2 5 7

1

</p>