Minimum Removals for Non-Decreasing Sequence

You are given a sequence of integers representing the heights of flowers. Your task is to determine the minimum number of flowers that must be removed so that the remaining flowers are arranged in a non-decreasing order.

This problem can be reformulated as follows: Let \(N\) be the total number of flowers and \(L\) be the length of the longest non-decreasing subsequence (LNDS) of the sequence. The answer is given by:

$$\text{MinRemovals} = N - L$$

For example, if the sequence is [5, 1, 6, 2, 3, 4] then the LNDS has a length of 4 (one possible LNDS is [1, 2, 3, 4]), and you must remove \(6 - 4 = 2\) flowers.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. For each test case, the first line contains an integer \(N\) representing the number of flowers. The second line contains \(N\) space-separated integers that represent the heights of the flowers.

outputFormat

For each test case, output a single integer on a new line, which is the minimum number of flowers to remove to obtain a non-decreasing sequence.

## sample

2
6
5 1 6 2 3 4
4
9 7 5 3

2
3

</p>