Minimum Removals to Sort Array

You are given an array of n integers. Your task is to determine the minimum number of elements to remove from the array such that the remaining sequence is in strictly increasing order.

This problem can be solved by finding the length of the longest increasing subsequence (LIS). The answer is given by the formula:

\( \text{Minimum Removals} = n - |\text{LIS}| \)

where \( |\text{LIS}| \) represents the length of the longest increasing subsequence in the array.

inputFormat

The input is given via standard input (stdin). The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer via standard output (stdout) denoting the minimum number of removals required so that the remaining array is strictly increasing.

5
3 4 2 1 5

2