Sorting Books with Minimum Moves

In this problem, you are given a sequence of books, each having a certain thickness. The books are arranged in an arbitrary order on a shelf. The goal is to determine the minimum number of moves required so that the books are arranged in non-decreasing order of thickness. In one move, you are allowed to remove a book from its current position and insert it at another position.

A key observation is that if you can find the longest sequence of books that appear in the correct sorted order (i.e., a subsequence that matches the sorted order), then the minimum number of moves required is the total number of books minus the length of this subsequence.

Formally, let (N) be the number of books, and let (A = [a_1, a_2, \dots, a_N]) be their thicknesses. Let (B = sorted(A)). Let (i) be the length of the longest prefix of (B) that can be found as a subsequence in (A). Then, the answer is (N-i).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. For each test case, the first line contains an integer (N), representing the number of books. The second line contains (N) space-separated integers denoting the thicknesses of the books.

outputFormat

For each test case, output a single line containing the minimum number of moves required to arrange the books in non-decreasing order.## sample

1
5
4 3 2 5 1

4