INVCNT

Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Input

The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i - 1] is given (A[i - 1] <= 10^7). The (n + 1)th line is a blank space.

Output

For every test output one line giving the number of inversions of A.

Example

Input:
2

3
3
1
2

5
2
3
8
6
1

Output:
2
5

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>

using namespace std;

unsigned long long counter;

void merge(vector<int> &A, int p, int q, int r) {  
    int n1 = q - p + 1,
        n2 = r - q;
    vector<int> L(n1 + 1), R(n2 + 1);
    for (int i = 0; i < n1; ++i) {
        L[i] = A[p + i];
    }
    for (int i = 0; i < n2; ++i) {
        R[i] = A[q + i + 1];
    }
    L[n1] = R[n2] = INT_MAX;
    int i = 0,
        j = 0;
    for (int k = p; k <= r; ++k) {
        if (L[i] <= R[j] && L[i] != INT_MAX) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
            counter += n1 - i;
        }
    }
    return;
}

void mergeSort(vector<int> &A, int p, int r) {  
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(A, p, q);
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

int main() {  
    int T;
    cin >> T;
    for (;T--;) {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }
        counter = 0;
        mergeSort(A, 0, N - 1);
        cout << counter << "\n";
    }
    return 0;
}