inversions

An inversion in a sequence A[1..n] is defined as i, j, 1 ≤ i < jn, such that A[i] > A[j]. For example, the sequence A = {1, 5, 2, 4, 3} contains 4 inversions, from the pairs (5, 2), (5, 4), (5, 3), (4, 3).

Your task is simple: Given a sequence, determine the number of inversions in the sequence.

Input

The first line of input will be an integer T (T ≤ 100), stating the number of test cases.

T test cases follow, each in the following format:

First line: An integer N (N ≤ 50,000),

Next line: N integers, giving the values of A[1], A[2], ..., A[N]. You may assume that 0 ≤ A[k] ≤ 2,147,483,647 for all kN.

Output

For each test case, output a single number: The number of inversions in the sequence.

Sample Input 1

3
5
1 5 2 4 3
5
1 2 3 4 5
6
6 5 4 3 2 1

Sample Output 1

4
0
15

Submitting .cpp to 'inversions'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 128MB
No. of ACs: 70
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 100
2 0