Murder

Once detective Saikat was solving a murder case. While going to the crime scene he took the stairs and saw that a number is written on every stair. He found it suspicious and decides to remember all the numbers that he has seen till now. While remembering the numbers he found that he can find some pattern in those numbers. So he decides that for each number on the stairs he will note down the sum of all the numbers previously seen on the stairs which are smaller than the present number. Calculate the sum of all the numbers written on his notes diary.

Answer may not fit in integer . You have to take long.

Input

First line gives T, number of test cases.

2T lines follow.

First line gives you the number of stairs N

Next line gives you N numbers written on the stairs.

Output

For each test case output one line giving the final sum for each test case.

Constraints

T<=10

1<=N<=10^5

All numbers will be between 0 and 10^6.

Sample Input:

1
5
1 5 3 6 4

Sample Output:

15

Explanation:

For the first number, the contribution to the sum is 0.
For the second number, the contribution to the sum is 1.
For the third number, the contribution to the sum is 1.
For the fourth number, the contribution to the sum is 9 (1+5+3).
For the fifth number, the contribution to the sum is 4 (1+3).
Hence the sum is 15 (0+1+1+9+4).

public class Main {
    public static long merge(int A[], int left, int right) {
        int mid = left + (right - left) / 2;
        int pointer1 = left, pointer2 = mid + 1, index = 0;
        int temp[] = new int[right - left + 1];
        long count = 0;
        while (pointer1 <= mid && pointer2 <= right) {
            // If arr[p1] is smaller that arr[p2], then arr[p1] will be smaller than all the
            // elements following arr[p2]
            if (A[pointer1] < A[pointer2]) {
                count += A[pointer1] * (right - pointer2 + 1);
                temp[index++] = A[pointer1++];
            } else
                temp[index++] = A[pointer2++];
        }
        while (pointer1 <= mid)
            temp[index++] = A[pointer1++];
        while (pointer2 <= right)
            temp[index++] = A[pointer2++];
        for (int i = left; i <= right; i++)
            A[i] = temp[i - left];
        return count;
    }

    public static long mergeSort(int arr[], int left, int right) {
        if (left >= right)
            return 0L;
        int mid = left + (right - left) / 2;
        long leftSum = mergeSort(arr, left, mid);
        long rightSum = mergeSort(arr, mid + 1, right);
        long mergeSum = merge(arr, left, right);
        return (mergeSum + leftSum + rightSum);
    }

    public static long requiredSum(int[] arr, int n) {
        return mergeSort(arr, 0, n - 1);
    }
}