#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

An inversion in a sequence *A*[1..*n*] is defined as *i*, *j*, 1 ≤ *i* < *j* ≤ *n*, 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 *k* ≤ *N*.

## 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 1 | 1s | 32MB | Average |

2 | 0 | 1 | 1s | 32MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o inversions -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512