Minimum Removals for Strictly Increasing Array

Given an integer array, determine the minimum number of elements to remove in order to make the remaining array strictly increasing. An array is strictly increasing if every element is greater than its preceding element.

For example, from the array [1, 3, 2, 4, 3, 5], by removing 2 elements, you can obtain [1, 3, 4, 5], which is strictly increasing.

This problem can be effectively solved by finding the length of the Longest Increasing Subsequence (LIS). The minimum removals required will be the total number of elements minus the length of the LIS.

The mathematical formulation is:

\[ \text{Minimum Removals} = N - \text{LIS Length} \]

inputFormat

The first line of input contains an integer N representing the number of elements in the array.

The second line contains N space-separated integers representing the elements of the array. If N is zero, the second line may be empty.

outputFormat

Output a single integer representing the minimum number of elements that must be removed to obtain a strictly increasing array.

6
1 3 2 4 3 5

2