Count Inversions

In this problem, you are given an array of integers and you need to count the number of inversions in the array. An inversion is a pair of indices ( (i, j) ) such that ( i < j ) and ( A[i] > A[j] ). This metric indicates how far the array is from being sorted in increasing order. A common approach to solve this problem is by modifying the merge sort algorithm to count inversions as you sort the array, achieving a time complexity of ( O(n \log n) ).

inputFormat

The input begins with an integer ( T ) denoting the number of test cases. Each test case consists of two lines. The first line contains an integer ( N ), the size of the array. The second line contains ( N ) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single integer on a new line representing the number of inversions in the given array.## sample

2
5
2 4 1 3 5
4
8 4 2 1

3
6