Minimum Removals for Strictly Increasing Buildings

You are given n buildings in a row, where the height of the i-th building is given by an integer. Your task is to remove as few buildings as possible so that the remaining buildings' heights are in strictly increasing order from left to right.

This problem can be reformulated using the concept of the Longest Increasing Subsequence (LIS). In particular, if the length of the longest increasing subsequence is L, then the answer is n - L.

Formally, given an integer \( n \) and a sequence of heights \( h_1, h_2, \ldots, h_n \), determine the minimum number of buildings to remove such that the subsequence (after removal) satisfies \( h_{i_1} < h_{i_2} < \cdots < h_{i_k} \) where \( k = L \) and \( i_1 < i_2 < \cdots < i_k \).

inputFormat

The first line contains a single integer n, the number of buildings.

The second line contains n space-separated integers representing the heights of the buildings.

\(1 \leq n \leq 10^5\) and the heights are positive integers.

outputFormat

Output a single integer denoting the minimum number of buildings that should be removed to make the heights of the remaining buildings strictly increasing.

## sample

6
3 2 5 1 7 4

3

</p>