Up and Down

You are given a sequence of distinct integers \(A = [A_1, A_2, \dots, A_N]\). Your goal is to rearrange this sequence into an up and down sequence.

A sequence is considered up and down if there exists an index \(m\) (where \(1 \le m \le N\)) such that: \(A_1 < A_2 < \dots < A_m > A_{m+1} > \dots > A_N\)

The rearrangement is accomplished by swapping two adjacent elements of the sequence at a time. Your task is to find the minimum number of such swaps needed to reach an up and down sequence.

Input

The first line of the input gives the number of test cases, \(T\). Test cases follow. Each test case begins with a line containing a single integer \(N\). The next line contains \(N\) distinct integers: \(A_1, A_2, \dots, A_N\).

Output

For each test case,y, is the minimum number of swaps required to rearrange \(A\) into an up and down sequence.

Constraints

• \(1 \le T \le 100\)
• \(1 \le N \le 1000\)
• \(0 \le A_i \le 10^9\)

Sample Input

2
3
1 2 3
5
1 8 10 3 7

Ejemplo de Salida

0
1

Source

Google Code Jam Archive