Minimum Removals to Make Array Non-decreasing

Given an array of integers, your task is to determine the minimum number of elements you need to remove so that the remaining array is non-decreasing. In other words, you need to make the array sorted in non-decreasing order. Mathematically, if the array has n elements and its longest increasing subsequence (LIS) has length \(|LIS|\), then the answer is \(n - |LIS|\). Note that in this problem, we assume that the array elements are distinct so that the LIS is well-defined.

inputFormat

The input consists of two lines:

• The first line contains a single integer n, representing the number of elements in the array.
• The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer: the minimum number of removals required to make the array non-decreasing.

6
5 3 4 7 2 8

2