Minimum Paintings Removal for Strictly Increasing Years

You are given the number of paintings and a list representing their creation years. Your task is to determine the minimum number of paintings to remove so that the remaining paintings have strictly increasing creation years. More formally, given an array (a) of (n) integers, you need to find the minimum number of removals such that the remaining array is strictly increasing. This is equivalent to keeping the longest strictly increasing subsequence and removing the rest, so the answer is (n - L), where (L) is the length of that subsequence. An efficient solution uses a binary search based method to compute (L) in (O(n \log n)) time.

inputFormat

The first line contains a single integer (n) — the number of paintings. If (n > 0), the second line contains (n) space‑separated integers representing the creation years of the paintings.

outputFormat

Output a single integer — the minimum number of paintings to remove so that the remaining paintings have strictly increasing creation years.## sample

7
1985 1985 1990 1992 1992 1992 2001

3