The chef has one array of N natural numbers (might be in sorted order). Cheffina challenges chef to find the total number of inversions in the array.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains two lines of input, $N$.
- N space-separated natural numbers. 

-----Output:-----
For each test case, output in a single line answer as the total number of inversions.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $1 \leq arr[i] \leq 10^5$

-----Sample Input:-----
1
5
5 4 1 3 2

-----Sample Output:-----
8

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def mergeSort(arr, n):
	temp_arr = [0] * n
	return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
	inv_count = 0
	if left < right:
		mid = (left + right) // 2
		inv_count += _mergeSort(arr, temp_arr, left, mid)
		inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
		inv_count += merge(arr, temp_arr, left, mid, right)
	return inv_count

def merge(arr, temp_arr, left, mid, right):
	i = left
	j = mid + 1
	k = left
	inv_count = 0
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			temp_arr[k] = arr[i]
			k += 1
			i += 1
		else:
			temp_arr[k] = arr[j]
			inv_count += mid - i + 1
			k += 1
			j += 1
	while i <= mid:
		temp_arr[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp_arr[k] = arr[j]
		k += 1
		j += 1
	for loop_var in range(left, right + 1):
		arr[loop_var] = temp_arr[loop_var]
	return inv_count
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(mergeSort(a, n))


def trans(arr, n):
	temp = [0] * n
	return change(arr, temp, 0, n - 1)

def change(arr, temp, left, right):
	rep = 0
	if left < right:
		mid = (left + right) // 2
		rep += change(arr, temp, left, mid)
		rep += change(arr, temp, mid + 1, right)
		rep += merge(arr, temp, left, mid, right)
	return rep

def merge(arr, temp, left, mid, right):
	i = left
	j = mid + 1
	k = left
	rep = 0
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			temp[k] = arr[i]
			k += 1
			i += 1
		else:
			temp[k] = arr[j]
			rep += mid - i + 1
			k += 1
			j += 1
	while i <= mid:
		temp[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp[k] = arr[j]
		k += 1
		j += 1
	for loop_var in range(left, right + 1):
		arr[loop_var] = temp[loop_var]
	return rep
t = int(input())
from collections import defaultdict
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	result = trans(arr, n)
	print(result)


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True

def mergeSort(arr, n):
	temp_arr = [0] * n
	return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
	inv_count = 0
	if left < right:
		mid = (left + right) // 2
		inv_count += _mergeSort(arr, temp_arr, left, mid)
		inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
		inv_count += merge(arr, temp_arr, left, mid, right)
	return inv_count

def merge(arr, temp_arr, left, mid, right):
	i = left
	j = mid + 1
	k = left
	inv_count = 0
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			temp_arr[k] = arr[i]
			k += 1
			i += 1
		else:
			temp_arr[k] = arr[j]
			inv_count += mid - i + 1
			k += 1
			j += 1
	while i <= mid:
		temp_arr[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp_arr[k] = arr[j]
		k += 1
		j += 1
	for loop_var in range(left, right + 1):
		arr[loop_var] = temp_arr[loop_var]
	return inv_count
for _ in range(int(inp())):
	n = int(inp())
	arr = lmp()
	print(mergeSort(arr, n))


def merge(A, aux, low, mid, high):
	k = i = low
	j = mid + 1
	inversionCount = 0
	while i <= mid and j <= high:
		if A[i] <= A[j]:
			aux[k] = A[i]
			i = i + 1
		else:
			aux[k] = A[j]
			j = j + 1
			inversionCount += mid - i + 1
		k = k + 1
	while i <= mid:
		aux[k] = A[i]
		k = k + 1
		i = i + 1
	for i in range(low, high + 1):
		A[i] = aux[i]
	return inversionCount

def mergeSort(A, aux, low, high):
	if high == low:
		return 0
	mid = low + (high - low >> 1)
	inversionCount = 0
	inversionCount += mergeSort(A, aux, low, mid)
	inversionCount += mergeSort(A, aux, mid + 1, high)
	inversionCount += merge(A, aux, low, mid, high)
	return inversionCount
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	aux = l.copy()
	print(mergeSort(l, aux, 0, len(l) - 1))


from sys import stdin, stdout

def mergeSort(arr, n):
	temp_arr = [0] * n
	return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
	inv_count = 0
	if left < right:
		mid = (left + right) // 2
		inv_count += _mergeSort(arr, temp_arr, left, mid)
		inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
		inv_count += merge(arr, temp_arr, left, mid, right)
	return inv_count

def merge(arr, temp_arr, left, mid, right):
	i = left
	j = mid + 1
	k = left
	inv_count = 0
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			temp_arr[k] = arr[i]
			k += 1
			i += 1
		else:
			temp_arr[k] = arr[j]
			inv_count += mid - i + 1
			k += 1
			j += 1
	while i <= mid:
		temp_arr[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp_arr[k] = arr[j]
		k += 1
		j += 1
	for loop_var in range(left, right + 1):
		arr[loop_var] = temp_arr[loop_var]
	return inv_count
test = int(stdin.readline())
for _ in range(test):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	result = mergeSort(arr, n)
	print(result)


def count_inversions(a):
	res = 0
	counts = [0] * (len(a) + 1)
	rank = {v: i + 1 for (i, v) in enumerate(sorted(a))}
	for x in reversed(a):
		i = rank[x] - 1
		while i:
			res += counts[i]
			i -= i & -i
		i = rank[x]
		while i <= len(a):
			counts[i] += 1
			i += i & -i
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(count_inversions(a))