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: interview

Starter code:

Solutions:
# cook your dish here
def mergeSort(arr, n): 
    # A temp_arr is created to store 
    # sorted array in merge function 
    temp_arr = [0]*n 
    return _mergeSort(arr, temp_arr, 0, n-1) 
  
# This Function will use MergeSort to count inversions 
  
def _mergeSort(arr, temp_arr, left, right): 
  
    # A variable inv_count is used to store 
    # inversion counts in each recursive call 
  
    inv_count = 0
  
    # We will make a recursive call if and only if 
    # we have more than one elements 
  
    if left < right: 
  
        # mid is calculated to divide the array into two subarrays 
        # Floor division is must in case of python 
  
        mid = (left + right)//2
  
        # It will calculate inversion  
        # counts in the left subarray 
  
        inv_count += _mergeSort(arr, temp_arr,  
                                    left, mid) 
  
        # It will calculate inversion  
        # counts in right subarray 
  
        inv_count += _mergeSort(arr, temp_arr,  
                                  mid + 1, right) 
  
        # It will merge two subarrays in  
        # a sorted subarray 
  
        inv_count += merge(arr, temp_arr, left, mid, right) 
    return inv_count 
  
# This function will merge two subarrays  
# in a single sorted subarray 
def merge(arr, temp_arr, left, mid, right): 
    i = left     # Starting index of left subarray 
    j = mid + 1 # Starting index of right subarray 
    k = left     # Starting index of to be sorted subarray 
    inv_count = 0
  
    # Conditions are checked to make sure that  
    # i and j don't exceed their 
    # subarray limits. 
  
    while i <= mid and j <= right: 
  
        # There will be no inversion if arr[i] <= arr[j] 
  
        if arr[i] <= arr[j]: 
            temp_arr[k] = arr[i] 
            k += 1
            i += 1
        else: 
            # Inversion will occur. 
            temp_arr[k] = arr[j] 
            inv_count += (mid-i + 1) 
            k += 1
            j += 1
  
    # Copy the remaining elements of left  
    # subarray into temporary array 
    while i <= mid: 
        temp_arr[k] = arr[i] 
        k += 1
        i += 1
  
    # Copy the remaining elements of right  
    # subarray into temporary array 
    while j <= right: 
        temp_arr[k] = arr[j] 
        k += 1
        j += 1
  
    # Copy the sorted subarray into Original array 
    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 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	 # Starting index of left subarray 
	j = mid + 1 # Starting index of right subarray 
	k = left	 # Starting index of to be sorted subarray 
	inv_count = 0

	# Conditions are checked to make sure that 
	# i and j don't exceed their 
	# subarray limits. 

	while i <= mid and j <= right: 

		# There will be no inversion if arr[i] <= arr[j] 

		if arr[i] <= arr[j]: 
			temp_arr[k] = arr[i] 
			k += 1
			i += 1
		else: 
			# Inversion will occur. 
			temp_arr[k] = arr[j] 
			inv_count += (mid-i + 1) 
			k += 1
			j += 1

	# Copy the remaining elements of left 
	# subarray into temporary array 
	while i <= mid: 
		temp_arr[k] = arr[i] 
		k += 1
		i += 1

	# Copy the remaining elements of right 
	# subarray into temporary array 
	while j <= right: 
		temp_arr[k] = arr[j] 
		k += 1
		j += 1

	# Copy the sorted subarray into Original array 
	for loop_var in range(left, right + 1): 
		arr[loop_var] = temp_arr[loop_var] 
		
	return inv_count 

# Driver Code 
# Given array is 
for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    result = mergeSort(arr, n) 
    print(result) 


# Python 3 program to count inversions in an array 

# Function to Use Inversion Count 
def mergeSort(arr, n): 
	# A temp_arr is created to store 
	# sorted array in merge function 
	temp_arr = [0]*n 
	return _mergeSort(arr, temp_arr, 0, n-1) 

# This Function will use MergeSort to count inversions 

def _mergeSort(arr, temp_arr, left, right): 

	# A variable inv_count is used to store 
	# inversion counts in each recursive call 

	inv_count = 0

	# We will make a recursive call if and only if 
	# we have more than one elements 

	if left < right: 

		# mid is calculated to divide the array into two subarrays 
		# Floor division is must in case of python 

		mid = (left + right)//2

		# It will calculate inversion 
		# counts in the left subarray 

		inv_count += _mergeSort(arr, temp_arr, 
									left, mid) 

		# It will calculate inversion 
		# counts in right subarray 

		inv_count += _mergeSort(arr, temp_arr, 
								mid + 1, right) 

		# It will merge two subarrays in 
		# a sorted subarray 

		inv_count += merge(arr, temp_arr, left, mid, right) 
	return inv_count 

# This function will merge two subarrays 
# in a single sorted subarray 
def merge(arr, temp_arr, left, mid, right): 
	i = left	 # Starting index of left subarray 
	j = mid + 1 # Starting index of right subarray 
	k = left	 # Starting index of to be sorted subarray 
	inv_count = 0

	# Conditions are checked to make sure that 
	# i and j don't exceed their 
	# subarray limits. 

	while i <= mid and j <= right: 

		# There will be no inversion if arr[i] <= arr[j] 

		if arr[i] <= arr[j]: 
			temp_arr[k] = arr[i] 
			k += 1
			i += 1
		else: 
			# Inversion will occur. 
			temp_arr[k] = arr[j] 
			inv_count += (mid-i + 1) 
			k += 1
			j += 1

	# Copy the remaining elements of left 
	# subarray into temporary array 
	while i <= mid: 
		temp_arr[k] = arr[i] 
		k += 1
		i += 1

	# Copy the remaining elements of right 
	# subarray into temporary array 
	while j <= right: 
		temp_arr[k] = arr[j] 
		k += 1
		j += 1

	# Copy the sorted subarray into Original array 
	for loop_var in range(left, right + 1): 
		arr[loop_var] = temp_arr[loop_var] 
		
	return inv_count 

# Driver Code 
# Given array is 
for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    result = mergeSort(arr, n) 
    print(result) 

# This code is contributed by ankush_953 


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

# Python 3 program to count inversions in an array 

# Function to Use Inversion Count 
def mergeSort(arr, n): 
	# A temp_arr is created to store 
	# sorted array in merge function 
	temp_arr = [0]*n 
	return _mergeSort(arr, temp_arr, 0, n-1) 

# This Function will use MergeSort to count inversions 

def _mergeSort(arr, temp_arr, left, right): 

	# A variable inv_count is used to store 
	# inversion counts in each recursive call 

	inv_count = 0

	# We will make a recursive call if and only if 
	# we have more than one elements 

	if left < right: 

		# mid is calculated to divide the array into two subarrays 
		# Floor division is must in case of python 

		mid = (left + right)//2

		# It will calculate inversion 
		# counts in the left subarray 

		inv_count += _mergeSort(arr, temp_arr, 
									left, mid) 

		# It will calculate inversion 
		# counts in right subarray 

		inv_count += _mergeSort(arr, temp_arr, 
								mid + 1, right) 

		# It will merge two subarrays in 
		# a sorted subarray 

		inv_count += merge(arr, temp_arr, left, mid, right) 
	return inv_count 

# This function will merge two subarrays 
# in a single sorted subarray 
def merge(arr, temp_arr, left, mid, right): 
	i = left	 # Starting index of left subarray 
	j = mid + 1 # Starting index of right subarray 
	k = left	 # Starting index of to be sorted subarray 
	inv_count = 0

	# Conditions are checked to make sure that 
	# i and j don't exceed their 
	# subarray limits. 

	while i <= mid and j <= right: 

		# There will be no inversion if arr[i] <= arr[j] 

		if arr[i] <= arr[j]: 
			temp_arr[k] = arr[i] 
			k += 1
			i += 1
		else: 
			# Inversion will occur. 
			temp_arr[k] = arr[j] 
			inv_count += (mid-i + 1) 
			k += 1
			j += 1

	# Copy the remaining elements of left 
	# subarray into temporary array 
	while i <= mid: 
		temp_arr[k] = arr[i] 
		k += 1
		i += 1

	# Copy the remaining elements of right 
	# subarray into temporary array 
	while j <= right: 
		temp_arr[k] = arr[j] 
		k += 1
		j += 1

	# Copy the sorted subarray into Original array 
	for loop_var in range(left, right + 1): 
		arr[loop_var] = temp_arr[loop_var] 
		
	return inv_count 

for i in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    result = mergeSort(arr, n) 
    print( result) 




def merge(A, aux, low, mid, high):
 
    k = i = low
    j = mid + 1
    inversionCount = 0
 
    # While there are elements in the left and right runs
    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)  # NOTE
 
        k = k + 1
 
    # Copy remaining elements
    while i <= mid:
        aux[k] = A[i]
        k = k + 1
        i = i + 1
 
    # Don't need to copy second half
 
    # copy back to the original list to reflect sorted order
    for i in range(low, high + 1):
        A[i] = aux[i]
 
    return inversionCount
 
 
# Sort list [low..high] using auxiliary space aux
def mergeSort(A, aux, low, high):
 
    # Base case
    if high == low:  # if run size == 1
        return 0
 
    # find mid point
    mid = low + ((high - low) >> 1)
    inversionCount = 0
 
    # recursively split runs into two halves until run size == 1,
    # then merge them and return back up the call chain
 
    inversionCount += mergeSort(A, aux, low, mid)        # split / merge left half
    inversionCount += mergeSort(A, aux, mid + 1, high)   # split / merge right half
    inversionCount += merge(A, aux, low, mid, high)      # merge the two half runs
 
    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))

# Function to Use Inversion Count 
def mergeSort(arr, n):
    # A temp_arr is created to store 
    # sorted array in merge function 
    temp_arr = [0] * n
    return _mergeSort(arr, temp_arr, 0, n - 1)


# This Function will use MergeSort to count inversions 

def _mergeSort(arr, temp_arr, left, right):
    # A variable inv_count is used to store 
    # inversion counts in each recursive call 

    inv_count = 0

    # We will make a recursive call if and only if 
    # we have more than one elements 

    if left < right:
        # mid is calculated to divide the array into two subarrays 
        # Floor division is must in case of python 

        mid = (left + right) // 2

        # It will calculate inversion  
        # counts in the left subarray 

        inv_count += _mergeSort(arr, temp_arr,
                                left, mid)

        # It will calculate inversion  
        # counts in right subarray 

        inv_count += _mergeSort(arr, temp_arr,
                                mid + 1, right)

        # It will merge two subarrays in  
        # a sorted subarray 

        inv_count += merge(arr, temp_arr, left, mid, right)
    return inv_count


# This function will merge two subarrays  
# in a single sorted subarray 
def merge(arr, temp_arr, left, mid, right):
    i = left  # Starting index of left subarray 
    j = mid + 1  # Starting index of right subarray 
    k = left  # Starting index of to be sorted subarray 
    inv_count = 0

    # Conditions are checked to make sure that  
    # i and j don't exceed their 
    # subarray limits. 

    while i <= mid and j <= right:

        # There will be no inversion if arr[i] <= arr[j] 

        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            k += 1
            i += 1
        else:
            # Inversion will occur. 
            temp_arr[k] = arr[j]
            inv_count += (mid - i + 1)
            k += 1
            j += 1

    # Copy the remaining elements of left  
    # subarray into temporary array 
    while i <= mid:
        temp_arr[k] = arr[i]
        k += 1
        i += 1

    # Copy the remaining elements of right  
    # subarray into temporary array 
    while j <= right:
        temp_arr[k] = arr[j]
        k += 1
        j += 1

    # Copy the sorted subarray into Original array 
    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())
    arr = list(map(int,input().split()))
    print(mergeSort(arr, n))


#https://www.geeksforgeeks.org/counting-inversions/
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))