truck-arrangement

There are N trucks that are participating at Independence day parade this year. Each truck is given a number. They go in the parade in the ascending order of those given numbers. In the morning of the parade day all the trucks arrive at a place from where they start. They might come in different order. So Jay has been assigned to arrange them in the order.

But unfortunately, Vinay, the person who allotted the numbers of ordering to the trucks is lazy enough to mess up things. He gave same number to multiple trucks. This surely makes Jay go mad off in ordering them. But believe in Jay. He makes the arrangement look good. He orders them in such a way that equal numbers are arranged in the sequence they are now in.

A truck can change from its current position to next position(Either front or back) in 1 minute. Imagine trucks are lying in a single lane and could pass through each other. Jay wants to find the minimum time it would take in arranging them.
Note that multiple trucks can change their position simultaneously.
Input Format:
First line contains T, number of test cases.
First line of every case contains a number(N) denoting number of Trucks that participate in parade.
Second line of every case contains N numbers(a1,a2,..ai,..aN) denoting the numbers of trucks they initially are arranged in.

Output Format:
Output the minimum time it takes to arrange the trucks as thought by Jay. Output of each case in a new line.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10000
1 ≤ ai ≤ 10000

Problem Setter : Vinay Kumar

Large I/O files. Use scanf() and printf() instead of cin and cout

SAMPLE INPUT
2
6
5 6 2 1 8 2
5
5 8 21 6 4

SAMPLE OUTPUT
3
4

Explanation

Test Case 1 : Given are six trucks (a1,a2,a3,a4,a5,a6) with numbers (5,6,2,1,8,2) respectively. After arranging them in the order as mentioned above, the numbers would in order of 1 2 2 5 6 8 (denoting trucks a4, a3, a6, a1, a2, a5). It takes 3 minutes for a1 to reach this position, after which the arrangement is complete.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: