Minimum Removals for Strictly Increasing Tree Heights

In this problem, you are given a list of N integers representing the heights of trees. Your goal is to remove the minimum number of trees so that the heights of the remaining trees form a strictly increasing sequence. In other words, find the minimum number of removals required such that if the remaining sequence is denoted by (a_1, a_2, \dots, a_k), then it satisfies (a_i < a_{i+1}) for all (1 \leq i < k).

For example, given the array [3, 1, 2, 1, 4, 5], removing two trees will produce a strictly increasing sequence. Your task is to implement a function that computes this minimum number of removals.

inputFormat

The input is read from standard input and consists of two lines. The first line contains an integer N, the number of trees. The second line contains N space-separated integers representing the heights of the trees.

outputFormat

The output, which should be written to standard output, is a single integer representing the minimum number of trees that must be removed so that the remaining trees have strictly increasing heights.## sample

6
3 1 2 1 4 5

2