Minimum Removal of Students for Sorted Height Sequence

You are given a row of students represented by their heights. Your task is to determine the minimum number of students to remove so that the remaining students form a strictly increasing or strictly decreasing sequence by height.

The input consists of an integer n followed by n positive integers denoting the heights of the students. You must compute and output the minimum number of removals needed to achieve one of these sorted orders.

Note: The sequence must be strictly monotonic (either strictly increasing or strictly decreasing).

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains a single integer n, 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 (stdout) representing the minimum number of students that need to be removed so that the remaining students are arranged in a strictly increasing or strictly decreasing order.

8
1 3 2 2 4 5 3 6

3