Minimum Operations to Achieve a Beautiful Array

An array is defined to be beautiful if it is sorted in non-decreasing order. In other words, an array \(a_1, a_2, \ldots, a_n\) is beautiful if \(a_1 \le a_2 \le \cdots \le a_n\).

You are given an array of integers. In one operation, you can select an element and change its value so that eventually the entire array becomes beautiful. However, it turns out that if you want to achieve a beautiful array, the minimum number of operations required is equal to the number of indices \(i\) for which \(a_i\) does not equal the \(i\)th element of the sorted version of the array.

Formally, let \(sorted(a)\) be the array obtained by sorting \(a\) in non-decreasing order. The answer is the number of indices \(i\) (with \(1 \le i \le n\)) such that \(a_i \neq sorted(a)_i\).

Your task is to compute this number for multiple test cases.

inputFormat

The first line of input contains an integer \(T\) (\(1 \le T \le 10^4\)) denoting the number of test cases.

For each test case, the first line contains an integer \(n\) (\(1 \le n \le 10^5\)) representing the number of elements in the array. The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) (\(|a_i| \le 10^9\)).

It is guaranteed that the sum of all \(n\) over all test cases does not exceed \(10^6\).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of operations required to make the array beautiful.

5
1 2 3 4 5

0