Minimum Removals to Sort Problems

You are given an array of integers representing the difficulties of several problems. Your task is to remove the minimum number of problems so that the remaining problems are in non-decreasing order.

This problem is equivalent to finding the longest non-decreasing subsequence (LNDS) in the array. Formally, if the length of the array is \(n\) and the length of the longest non-decreasing subsequence is \(L\), then the answer is:

\(n - L\)

Ensure your program reads input from stdin and writes the answer to stdout.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of problems.
2. The second line contains \(n\) space-separated integers, each representing the difficulty of a problem.

outputFormat

Output a single integer, which is the minimum number of problems to remove so that the remaining problems are sorted in non-decreasing order.

5
5 3 4 8 6

2