Minimum Removals for Strictly Increasing Heights

Given an array of integers representing the heights of students, determine the minimum number of students to remove so that the remaining sequence of heights is strictly increasing.

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

$$\text{removals} = n - |LIS|$$

where \( n \) is the total number of students and \(|LIS|\) is the length of the longest increasing subsequence.

inputFormat

The input is read from standard input. It consists of two lines:

• The first line contains a single integer \( n \) representing the number of students.
• The second line contains \( n \) space-separated integers representing the heights of the students.

outputFormat

Output a single integer to standard output representing the minimum number of students to remove so that the remaining sequence of heights is strictly increasing.

## sample

6
5 3 4 8 6 7

2

</p>