Insertion Sort is a simple sorting technique which was covered in previous challenges. Sometimes, arrays may be too large for us to wait around for insertion sort to finish. Is there some other way we can calculate the number of shifts an insertion sort performs when sorting an array?

If $k[i]$ is the number of elements over which the $i^{\mbox{th}}$ element of the array has to shift, then the total number of shifts will be $k[1]+k[2]+$ ... + $k[n]$.  

Example 

$arr=[4,3,2,1]$  

Array		Shifts
[4,3,2,1]	
[3,4,2,1]	1
[2,3,4,1]	2
[1,2,3,4]	3

Total shifts = 1 + 2 + 3 = 6

Function description  

Complete the insertionSort function in the editor below.   

insertionSort has the following parameter(s):  

int arr[n]: an array of integers  

Returns 

- int: the number of shifts required to sort the array

Input Format

The first line contains a single integer $\boldsymbol{\boldsymbol{t}}$, the number of queries to perform. 

The following $\boldsymbol{\boldsymbol{t}}$ pairs of lines are as follows:  

The first line contains an integer $n$, the length of $\textbf{arr}$.
The second line contains $n$ space-separated integers $arr\left[i\right]$.

Constraints

$1\leq t\leq15$  
$1\leq n\leq1000000$  
$1\leq a[i]\leq1000000$

Sample Input
2  
5  
1 1 1 2 2  
5  
2 1 3 1 2

Sample Output
0  
4   

Explanation

The first query is already sorted, so there is no need to shift any elements. In the second case, it will proceed in the following way.

Array: 2 1 3 1 2 -> 1 2 3 1 2 -> 1 1 2 3 2 -> 1 1 2 2 3
Moves:   -        1       -    2         -  1            = 4

Source: hackerrank | Difficulty: HARD
Tags: Sorting


Solutions:
def mergeSort(m):
	if len(m) <= 1:
		return [0, m]
	mid = len(m) // 2
	l = []
	r = []
	for i in range(mid):
		l.append(m[i])
	for i in range(mid, len(m)):
		r.append(m[i])
	left = mergeSort(l)
	right = mergeSort(r)
	return merge(left, right)

def merge(left, right):
	i = 0
	j = 0
	result = []
	num = left[0] + right[0]
	while i < len(left[1]) or j < len(right[1]):
		if i < len(left[1]) and j < len(right[1]):
			if left[1][i] <= right[1][j]:
				result.append(left[1][i])
				i += 1
				num += j
			else:
				result.append(right[1][j])
				j += 1
		elif i < len(left[1]):
			result.append(left[1][i])
			i += 1
			num += j
		elif j < len(right[1]):
			result.append(right[1][j])
			j += 1
	return [num, result]
T = int(input())
for i in range(T):
	n = int(input())
	nums = [int(i) for i in input().split()]
	print(mergeSort(nums)[0])


def countP(A):

	def sub(i, j):
		if j - i < 2:
			return 0
		else:
			me = (i + j) // 2
			rt = sub(i, me) + sub(me, j)
			tmp = []
			(l, r) = (i, me)
			while l < me and r < j:
				if A[l] > A[r]:
					tmp.append(A[r])
					r += 1
					rt += me - l
				else:
					tmp.append(A[l])
					l += 1
			while l < me:
				tmp.append(A[l])
				l += 1
			while r < j:
				tmp.append(A[r])
				r += 1
			A[i:j] = tmp
			return rt
	return sub(0, len(A))
T = int(input())
for t in range(T):
	n = int(input())
	print(countP([int(i) for i in input().split()]))


import sys

def merge(ar, left, right):
	(i, j, n) = (0, 0, 0)
	while i < len(left) or j < len(right):
		if i == len(left):
			ar[i + j] = right[j]
			j += 1
		elif j == len(right) or left[i] <= right[j]:
			ar[i + j] = left[i]
			i += 1
		else:
			ar[i + j] = right[j]
			j += 1
			n += len(left) - i
	return n

def inversion_count(ar):
	if len(ar) <= 1:
		return 0
	left = ar[:(len(ar) + 1) // 2]
	right = ar[(len(ar) + 1) // 2:]
	return inversion_count(left) + inversion_count(right) + merge(ar, left, right)
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	ar = list(map(int, sys.stdin.readline().split()))
	print(inversion_count(ar))


import copy

class Bit:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.data = [0] * sz

	def sum(self, i):
		assert i > 0
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		assert i > 0
		while i < self.size:
			self.data[i] += x
			i += i & -i

def maxValue(ar):
	max = 0
	for i in ar:
		if i > max:
			max = i
			continue
	return max

def inversions(arToCountShift):
	res = 0
	bit = Bit(maxValue(arToCountShift))
	for (i, v) in enumerate(arToCountShift):
		res += i - bit.sum(v)
		bit.add(v, 1)
	return res

def printArrayAsString(arToPrint):
	arStringInt = []
	for i in arToPrint:
		arStringInt.append(str(i))
	print(' '.join(arStringInt))

def insertSort(arIntToSort):
	numOcurence = 0
	for index in range(1, len(arIntToSort)):
		valueToInsert = arIntToSort[index]
		holePos = index
		while holePos > 0 and valueToInsert < arIntToSort[holePos - 1]:
			arIntToSort[holePos] = arIntToSort[holePos - 1]
			holePos = holePos - 1
			numOcurence = numOcurence + 1
		arIntToSort[holePos] = valueToInsert
	return numOcurence

def main():
	strNumTestCase = input()
	intNumTestCase = int(strNumTestCase)
	for i in range(intNumTestCase):
		strLengthArray = input()
		intLengthArray = int(strLengthArray)
		strValidArray = input()
		arStringValidArray = strValidArray.split()
		arIntValidArray = []
		for val in arStringValidArray:
			arIntValidArray.append(int(val))
		print(inversions(arIntValidArray))

def main2():
	strLengthArray = input()
	intLengthArray = int(strLengthArray)
	strValidArray = input()
	arStringValidArray = strValidArray.split()
	arIntValidArray = []
	for val in arStringValidArray:
		arIntValidArray.append(int(val))
	insertSort(arIntValidArray)
main()


def merge_count_split_inversion(left, right):
	result = []
	count = 0
	(i, j) = (0, 0)
	left_len = len(left)
	while i < left_len and j < len(right):
		if left[i] <= right[j]:
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			count += left_len - i
			j += 1
	result += left[i:]
	result += right[j:]
	return (result, count)

def merge_count_inversion(lst):
	if len(lst) <= 1:
		return (lst, 0)
	middle = int(len(lst) / 2)
	(left, a) = merge_count_inversion(lst[:middle])
	(right, b) = merge_count_inversion(lst[middle:])
	(result, c) = merge_count_split_inversion(left, right)
	return (result, a + b + c)

def count_inversion(lst):
	return merge_count_inversion(lst)[1]
n = int(input())
dct = {}
for i in range(n):
	k = int(input())
	a = input()
	dct.update({i: [int(x) for x in a.split()]})
for i in range(n):
	print(count_inversion(dct[i]))


import re, sys, os
mx = 1000000

def find_low(bit, id):
	ans = 0
	while id > 0:
		ans += bit[id]
		id ^= id & -id
	return ans

def add_bit(bit, id):
	while id < mx:
		bit[id] += 1
		id += id & -id

def gao():
	bit = [0] * mx
	len = int(input())
	v = [i for i in map(int, input().split())]
	v.reverse()
	ans = 0
	for i in v:
		ans += find_low(bit, i - 1)
		add_bit(bit, i)
	print(ans)

def main():
	if os.path.exists('in.txt'):
		sys.stdin = open('in.txt')
	for i in range(int(input())):
		gao()
main()


import math

def merge_sort(A):
	if len(A) <= 1:
		return (0, A)
	middle = math.floor(len(A) / 2)
	(left_inversions, left) = merge_sort(A[:middle])
	(right_inversions, right) = merge_sort(A[middle:])
	(merge_inversions, merged) = merge(left, right)
	inversions = left_inversions + right_inversions + merge_inversions
	return (inversions, merged)

def merge(left, right):
	result = []
	(i, j, inversions) = (0, 0, 0)
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			inversions += j
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	inversions += j * (len(left) - i)
	result += left[i:]
	result += right[j:]
	return (inversions, result)

def main():
	t = int(input())
	for x in range(1, t + 1):
		n = int(input())
		A = input()
		A = A.split()
		A = [int(x) for x in A]
		(inversions, merged) = merge_sort(A)
		print(inversions)
main()


from bisect import bisect_left

def find_ways():
	num_tests = int(input())
	input_lines = []
	for i in range(num_tests):
		input()
		input_lines.append(str(input()).strip())
	for line in input_lines:
		cheeky_sort([int(x) for x in line.split(' ')])

def cheeky_sort(listwa):
	num_swaps = 0
	sorted_list = sorted(listwa)
	for elem in listwa:
		elem_index = binary_search(sorted_list, elem)
		num_swaps += elem_index
		del sorted_list[elem_index]
	print(num_swaps)

def binary_search(a, x, lo=0, hi=None):
	hi = hi if hi is not None else len(a)
	pos = bisect_left(a, x, lo, hi)
	return pos if pos != hi and a[pos] == x else -1

def ins_sort(listwa):
	num_swaps = 0
	for i in range(1, len(listwa)):
		item = listwa[i]
		j = 0
		for j in range(i - 1, -1, -1):
			if item < listwa[j]:
				listwa[j + 1] = listwa[j]
				num_swaps += 1
			else:
				j += 1
				break
		listwa[j] = item
	print(num_swaps)

def print_all(list):
	for item in list:
		print(item, end=' ')

def main():
	find_ways()
main()


def merge(left, right):
	result = []
	(i, j, inversions) = (0, 0, 0)
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			inversions += j
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	inversions += j * (len(left) - i)
	result += left[i:]
	result += right[j:]
	return (inversions, result)

def merge_sort(A):
	if len(A) <= 1:
		return (0, A)
	middle = len(A) // 2
	(left_inversions, left) = merge_sort(A[:middle])
	(right_inversions, right) = merge_sort(A[middle:])
	(merge_inversions, merged) = merge(left, right)
	inversions = left_inversions + right_inversions + merge_inversions
	return (inversions, merged)
for _ in range(int(input())):
	N = input()
	a = [int(i) for i in input().split()]
	print(merge_sort(a)[0])


import bisect
t = int(input())
for j in range(t):
	size = int(input())
	v = [int(i) for i in input().strip().split()]
	v2 = []
	s = 0
	for (i, e) in enumerate(v):
		ind = bisect.bisect(v2, e)
		v2.insert(ind, e)
		s += i - ind
	print(s)


def merge(v, start, end):
	if end - start <= 1:
		return 0
	if end - start == 2:
		if v[start] > v[start + 1]:
			tmp = v[start]
			v[start] = v[start + 1]
			v[start + 1] = tmp
			return 1
		return 0
	mid = start + (end - start) // 2
	count = merge(v, start, mid) + merge(v, mid, end)
	v1 = v[start:mid]
	index = start
	(i, j) = (0, mid)
	while i < len(v1) and j < end:
		if v1[i] <= v[j]:
			v[index] = v1[i]
			i += 1
		elif v1[i] > v[j]:
			v[index] = v[j]
			count += mid - start - i
			j += 1
		index += 1
	while i < len(v1):
		v[index] = v1[i]
		index += 1
		i += 1
	while j < end:
		v[index] = v[j]
		index += 1
		j += 1
	return count
nn = int(input())
for ni in range(0, nn):
	n = int(input())
	vec = list(map(int, input().split()))
	print(merge(vec, 0, len(vec)))


def merge_sort(A):
	if len(A) <= 1:
		return (0, A)
	middle = int(len(A) / 2)
	(left_inversions, left) = merge_sort(A[:middle])
	(right_inversions, right) = merge_sort(A[middle:])
	(merge_inversions, merged) = merge(left, right)
	inversions = left_inversions + right_inversions + merge_inversions
	return (inversions, merged)

def merge(left, right):
	result = []
	(i, j, inversions) = (0, 0, 0)
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			inversions += j
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	inversions += j * (len(left) - i)
	result += left[i:]
	result += right[j:]
	return (inversions, result)
i = int(input())
j = 0
while j < i:
	array_size = int(input())
	array = [int(i) for i in input().strip().split(' ')]
	(inv, merged) = merge_sort(array)
	print(inv)
	j += 1


def add(ft, index, diff, n):
	while index <= n:
		ft[index] += diff
		index += index & -index

def prefixSum(ft, index):
	sum = 0
	while index > 0:
		sum += ft[index]
		index = index & index - 1
	return sum
caseCnt = int(input())
for caseNr in range(caseCnt):
	input()
	sum = 0
	n = 1000000
	fenwick = [0] * (n + 1)
	for k in input().split():
		k = int(k)
		add(fenwick, k, 1, n)
		sum += prefixSum(fenwick, n) - prefixSum(fenwick, k)
	print(sum)


from itertools import zip_longest

def inversion_number(a):
	res = 0
	lists = [[x] for x in a]
	while len(lists) > 1:
		pairs = list(zip_longest(*[iter(lists)] * 2))
		lists = []
		for (a1, a2) in pairs:
			if a2 == None:
				lists.append(a1)
			else:
				m = []
				(i, j) = (0, 0)
				while i < len(a1) and j < len(a2):
					if a1[i] <= a2[j]:
						m.append(a1[i])
						i += 1
					else:
						m.append(a2[j])
						res += len(a1) - i
						j += 1
				m.extend(a1[i:])
				m.extend(a2[j:])
				lists.append(m)
	return res
T = int(input())
for case in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	print(inversion_number(a))


from bisect import bisect_right
from array import array
import sys
readinput = sys.stdin.readline

def process(size):
	elems = array('i')
	inp = (int(x) for x in readinput().split())
	miss = 0
	for x in inp:
		idx = bisect_right(elems, x)
		miss += len(elems) - idx
		elems.insert(idx, x)
	return miss
number_of_cases = int(readinput())
for i in range(number_of_cases):
	sz = int(readinput())
	print(process(sz))


def SortInverse(array):
	if len(array) == 1:
		return (array, 0)
	else:
		result1 = SortInverse(array[:len(array) // 2])
		result2 = SortInverse(array[len(array) // 2:])
		left = result1[0]
		right = result2[0]
	inv = result1[1] + result2[1]
	i = 0
	j = 0
	k = 0
	while k < len(array):
		if i >= len(left):
			array[k] = right[j]
			j += 1
		elif j >= len(right):
			array[k] = left[i]
			i += 1
		elif left[i] <= right[j]:
			array[k] = left[i]
			i += 1
		else:
			array[k] = right[j]
			inv += len(left) - i
			j += 1
		k += 1
	return (array, inv)

def main():
	t = int(input())
	for l in range(t):
		n = input()
		numbers = list(map(int, input().split()))
		result = SortInverse(numbers)
		print(result[1])
main()


def merge(a, p, q, r):
	left = a[p:q + 1]
	right = a[q + 1:r + 1]
	m = q + 1 - p
	n = r - q
	i = 0
	j = 0
	move = 0
	for k in range(p, r + 1):
		if j >= n or (i < m and left[i] <= right[j]):
			a[k] = left[i]
			i += 1
		else:
			a[k] = right[j]
			j += 1
			move += m - i
	return move

def ins_count(a, p, r):
	if p >= r:
		return 0
	q = int((p + r) / 2)
	x = ins_count(a, p, q)
	y = ins_count(a, q + 1, r)
	z = merge(a, p, q, r)
	return x + y + z
T = int(input())
for _ in range(T):
	N = int(input())
	a = [int(c) for c in input().split()[:N]]
	print(ins_count(a, 0, N - 1))


def merge(left, right):
	l = len(left)
	r = len(right)
	i = j = count = 0
	d = []
	for k in range(l + r):
		if i == l:
			d.extend(right[j:])
			break
		elif j == r:
			d.extend(left[i:])
			break
		if left[i] <= right[j]:
			d.append(left[i])
			i += 1
		else:
			d.append(right[j])
			j += 1
			count += l - i
	return (d, count)

def sortcount(a):
	n = len(a)
	if n == 1:
		return (a, 0)
	mid = int(n / 2)
	left = a[:mid]
	right = a[mid:]
	(sleft, lc) = sortcount(left)
	(sright, rc) = sortcount(right)
	(d, count) = merge(sleft, sright)
	t = lc + rc + count
	return (d, t)
c = int(input())
for i in range(c):
	n = int(input())
	l = [int(x) for x in input().strip().split()]
	assert n == len(l)
	(l, count) = sortcount(l)
	print(count)


import bisect
t = int(input())
for _ in range(t):
	input()
	a = input().split()
	n = len(a)
	b = sorted(range(n), key=lambda i: int(a[i]))
	b.reverse()
	seen = []
	s = 0
	for i in b:
		s += bisect.bisect(seen, i)
		bisect.insort(seen, i)
	print(s)


class BIT:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.data = [0] * sz

	def g_sum(self, i):
		s = 0
		while i < self.size:
			s += self.data[i]
			i += i & -i
		return s

	def add(self, i):
		while i > 0:
			self.data[i] += 1
			i -= i & -i
num_tests = int(input())
for test in range(num_tests):
	array_size = int(input())
	array = [int(x) for x in input().split()]
	total_shifts = 0
	bit = BIT(1000000)
	for x in array:
		bit.add(x)
		total_shifts += bit.g_sum(x + 1)
	print(total_shifts)


_inv_count = 0

def count_exchanges(lst):
	global _inv_count
	_inv_count = 0
	_merge_sort(lst)
	return _inv_count

def _merge(left, right):
	result = []
	i = j = 0
	global _inv_count
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			result.append(left[i])
			i += 1
		else:
			_inv_count += len(left) - i
			result.append(right[j])
			j += 1
	for k in range(i, len(left)):
		result.append(left[k])
	for k in range(j, len(right)):
		result.append(right[k])
	return result

def _merge_sort(lst):
	if len(lst) < 2:
		return lst
	mid = len(lst) // 2
	left = _merge_sort(lst[:mid])
	right = _merge_sort(lst[mid:])
	return _merge(left, right)
t = int(input())
for _ in range(t):
	_ = input()
	lst = [int(el) for el in input().strip().split()]
	print(count_exchanges(lst))


import bisect
T = int(input())
for testcase_i in range(T):
	N = int(input())
	a_is = [int(x) for x in input().split()]
	s = []
	shift_total = 0
	for a_i in a_is:
		shift_total += bisect.bisect_right(s, a_i)
		bisect.insort_right(s, a_i)
	print(N * (N - 1) // 2 - shift_total)


def merge_sort(A):
	if len(A) <= 1:
		return (0, A)
	middle = len(A) // 2
	(left_inversions, left) = merge_sort(A[:middle])
	(right_inversions, right) = merge_sort(A[middle:])
	(merge_inversions, merged) = merge(left, right)
	inversions = left_inversions + right_inversions + merge_inversions
	return (inversions, merged)

def merge(left, right):
	result = []
	(i, j, inversions) = (0, 0, 0)
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			inversions += j
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	inversions += j * (len(left) - i)
	result += left[i:]
	result += right[j:]
	return (inversions, result)
cases = int(input())
for _ in range(0, cases):
	size = int(input())
	ar = list(map(int, input().split()))
	(inv, merged) = merge_sort(ar)
	print(inv)


import sys

def merge_count(ar, left, right):
	(i, j, n) = (0, 0, 0)
	while i < len(left) or j < len(right):
		if i == len(left):
			ar[i + j] = right[j]
			j += 1
		elif j == len(right) or left[i] <= right[j]:
			ar[i + j] = left[i]
			i += 1
		else:
			ar[i + j] = right[j]
			j += 1
			n += len(left) - i
	return n

def inversion_count(ar):
	if len(ar) <= 1:
		return 0
	left = ar[:(len(ar) + 1) // 2]
	right = ar[(len(ar) + 1) // 2:]
	return inversion_count(left) + inversion_count(right) + merge_count(ar, left, right)
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	ar = list(map(int, sys.stdin.readline().split()))
	print(inversion_count(ar))


class BIT:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.data = [0] * sz

	def add(self, index, v):
		while index < self.size:
			self.data[index] += v
			index += index & -index

	def sum(self, index):
		s = 0
		while index > 0:
			s += self.data[index]
			index -= index & -index
		return s

def calc(n, arr):
	bit = BIT(max(arr))
	result = 0
	for (i, v) in enumerate(arr):
		result += i - bit.sum(v)
		bit.add(v, 1)
	return result
T = int(input().strip())
for t in range(T):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split()]
	print(calc(n, arr))


import sys, math

def InversionCount(a):
	if len(a) < 2:
		return (0, a)
	m = int(len(a) / 2)
	a1 = a[:]
	(tmp, l) = InversionCount(a[:m])
	c = tmp
	(tmp, r) = InversionCount(a[m:])
	c += tmp
	i = 0
	while l and r:
		if l[0] <= r[0]:
			a[i] = l.pop(0)
		else:
			c += len(l)
			a[i] = r.pop(0)
		i += 1
	while l:
		a[i] = l.pop(0)
		i += 1
	while r:
		a[i] = r.pop(0)
		i += 1
	return (c, a)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(InversionCount(a)[0])


def mergeSort(alist, m):
	if len(alist) > 1:
		mid = len(alist) // 2
		lefthalf = alist[:mid]
		righthalf = alist[mid:]
		mergeSort(lefthalf, m)
		mergeSort(righthalf, m)
		i = 0
		j = 0
		k = 0
		while i < len(lefthalf) and j < len(righthalf):
			if lefthalf[i] <= righthalf[j]:
				alist[k] = lefthalf[i]
				i = i + 1
			else:
				m[0] = m[0] + len(lefthalf) - i
				alist[k] = righthalf[j]
				j = j + 1
			k = k + 1
		while i < len(lefthalf):
			alist[k] = lefthalf[i]
			i = i + 1
			k = k + 1
		while j < len(righthalf):
			alist[k] = righthalf[j]
			j = j + 1
			k = k + 1
n = int(input())
for _ in range(n):
	m = [0]
	nn = int(input())
	ar = [int(x) for x in input().split()]
	mergeSort(ar, m)
	for mm in m:
		print(mm)


get_int = lambda : int(input())
get_list = lambda : [int(s) for s in input().split()]
items = []

def reverse_pairs(left, right):
	if left + 1 >= right:
		return 0
	mid = (left + right) // 2
	cnt = reverse_pairs(left, mid) + reverse_pairs(mid, right)
	(i, j, tmp) = (left, mid, [])
	while i < mid and j < right:
		if items[i] <= items[j]:
			tmp.append(items[i])
			i += 1
		else:
			cnt += mid - i
			tmp.append(items[j])
			j += 1
	tmp.extend(items[i:mid] + items[j:right])
	items[left:right] = tmp
	return cnt
for _ in range(get_int()):
	n = get_int()
	items = get_list()
	print(reverse_pairs(0, n))


for T in range(int(input())):
	(N, a, ans) = (int(input()), [0] * 1000001, 0)
	for i in input().split():
		x = int(i)
		while x > 0:
			ans += a[x]
			x -= x & -x
		x = int(i)
		while x <= 1000000:
			a[x] += 1
			x += x & -x
	ans = N * (N - 1) // 2 - ans
	print(ans)


import sys

def merge(ar, left, right):
	(i, j, n) = (0, 0, 0)
	while i < len(left) or j < len(right):
		if i == len(left):
			ar[i + j] = right[j]
			j += 1
		elif j == len(right) or left[i] <= right[j]:
			ar[i + j] = left[i]
			i += 1
		else:
			ar[i + j] = right[j]
			j += 1
			n += len(left) - i
	return n

def inversion_count(ar):
	if len(ar) <= 1:
		return 0
	left = ar[:(len(ar) + 1) // 2]
	right = ar[(len(ar) + 1) // 2:]
	return inversion_count(left) + inversion_count(right) + merge(ar, left, right)
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	ar = list(map(int, sys.stdin.readline().split()))
	print(inversion_count(ar))


from functools import reduce

def bsize(n):
	if n == None:
		return 0
	return n[3]

def bgreater(n, v):
	if n == None:
		return 0
	(nv, l, r, s) = n
	if nv > v:
		return 1 + bgreater(l, v) + bsize(r)
	else:
		return bgreater(r, v)

def rebuildingInsert(n, v):
	if n == None:
		return (v, None, None, 1)
	(nv, l, r, s) = n
	if nv > v:
		if bsize(l) / s > 2 / 3:
			return rebuildingInsert(rebuild(n), v)
		else:
			return (nv, rebuildingInsert(l, v), r, s + 1)
	else:
		if bsize(r) / s > 2 / 3:
			return rebuildingInsert(rebuild(n), v)
		return (nv, l, rebuildingInsert(r, v), s + 1)

def traverse(n):
	if n == None:
		return
	(nv, l, r, s) = n
	yield from traverse(l)
	yield nv
	yield from traverse(r)

def rebuild_step(A, l, h):
	if h <= l:
		return None
	i = (l + h) // 2
	return (A[i], rebuild_step(A, l, i), rebuild_step(A, i + 1, h), h - l)

def rebuild(n):
	jks = list(traverse(n))
	return rebuild_step(jks, 0, len(jks))

def count(A):
	if list(sorted(A)) == A:
		return 0
	if list(sorted(reversed(A))) == list(reversed(A)):
		return len(A) * (len(A) - 1) // 2
	return reduce(lambda x, y: (x[0] + bgreater(x[1], y), rebuildingInsert(x[1], y)), A, (0, None))[0]
for i in range(int(input())):
	input()
	print(count(list(map(int, input().split()))))


def merge_sort(A):
	if len(A) <= 1:
		return (0, A)
	middle = int(len(A) / 2)
	(left_inversions, left) = merge_sort(A[:middle])
	(right_inversions, right) = merge_sort(A[middle:])
	(merge_inversions, merged) = merge(left, right)
	inversions = left_inversions + right_inversions + merge_inversions
	return (inversions, merged)

def merge(left, right):
	result = []
	(i, j, inversions) = (0, 0, 0)
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			inversions += j
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	inversions += j * (len(left) - i)
	result += left[i:]
	result += right[j:]
	return (inversions, result)
t = int(input())
while t:
	t -= 1
	n = input()
	numbers = [int(x) for x in input().split()]
	(result, numbers) = merge_sort(numbers)
	print(result)


import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	after_sort = list()
	count = 0
	for idx in range(n):
		insert_index = bisect.bisect_right(after_sort, nums[idx], 0, idx)
		count = count + (idx - insert_index)
		after_sort.insert(insert_index, nums[idx])
	print(count)


def split_inversion_pairs(a, l, r):
	index = 0
	(li, ri) = (0, 0)
	count = 0
	while li < len(l) and ri < len(r):
		if l[li] <= r[ri]:
			a[index] = l[li]
			(li, index) = (li + 1, index + 1)
		else:
			count += len(l) - li
			a[index] = r[ri]
			(ri, index) = (ri + 1, index + 1)
	if li < len(l):
		while li < len(l):
			a[index] = l[li]
			(li, index) = (li + 1, index + 1)
	elif ri < len(r):
		while ri < len(r):
			a[index] = r[ri]
			(ri, index) = (ri + 1, index + 1)
	return count

def inversion_pairs(array):
	if len(array) == 1:
		return 0
	(left, right) = (array[:len(array) // 2], array[len(array) // 2:])
	return inversion_pairs(left) + inversion_pairs(right) + split_inversion_pairs(array, left, right)
T = int(input())
for _ in range(T):
	N = int(input())
	arr = [int(x) for x in input().split()]
	print(inversion_pairs(arr))


def merge(l, r, c):
	res = []
	while len(l) > 0 and len(r) > 0:
		if l[0] <= r[0]:
			res.append(l.pop(0))
		else:
			res.append(r.pop(0))
			c[0] = c[0] + len(l)
	res.extend(l)
	res.extend(r)
	return res

def merge_sort(a, n, c):
	if n <= 1:
		return a
	m = int(n / 2)
	l = a[:m]
	r = a[m:]
	l = merge_sort(l, m, c)
	r = merge_sort(r, n - m, c)
	return merge(l, r, c)
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().strip().split(' ')))
	c = [0]
	merge_sort(a, n, c)
	print(c[0])


res = []

def msort(L):
	if len(L) == 1:
		return L
	else:
		temp1 = msort(L[:len(L) // 2])
		temp2 = msort(L[len(L) // 2:])
		return merge(temp1, temp2)

def merge(L, M):
	temp = []
	(l1, l2) = (len(L), len(M))
	(pos1, pos2, count) = (0, 0, 0)
	while count < l1 + l2:
		if pos1 < l1 and pos2 < l2:
			if L[pos1] <= M[pos2]:
				temp.append(L[pos1])
				count += 1
				pos1 += 1
				res.append(pos2)
			else:
				temp.append(M[pos2])
				count += 1
				pos2 += 1
		elif pos1 < l1:
			temp.append(L[pos1])
			count += 1
			pos1 += 1
			res.append(pos2)
		else:
			temp.append(M[pos2])
			count += 1
			pos2 += 1
	return temp
t = int(input())
for i in range(t):
	res = []
	n = int(input())
	l = [int(i) for i in input().split()]
	temp = msort(l)
	print(sum(res))


def merge(left, right):
	res = []
	(i, j, swaps) = (0, 0, 0)
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			res.append(left[i])
			i += 1
			swaps += j
		else:
			res.append(right[j])
			j += 1
	swaps += j * (len(left) - i)
	res += left[i:]
	res += right[j:]
	return (res, swaps)

def merge_sort(a):
	if len(a) == 1:
		return (a, 0)
	m = len(a) // 2
	(left, left_swaps) = merge_sort(a[:m])
	(right, right_swaps) = merge_sort(a[m:])
	(merged, merge_swaps) = merge(left, right)
	return (merged, left_swaps + right_swaps + merge_swaps)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	(_, res) = merge_sort(a)
	print(res)


def add(c, v):
	i = l + v
	while i >= 0:
		c[i] += 1
		i = (i - 1) // 2

def loc(c, v):
	i = l + v
	s = c[i]
	r = False
	while i >= 0:
		if r:
			s += c[2 * i + 1]
		r = i % 2 == 0
		i = (i - 1) // 2
	return s
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = [0] * (2 ** 21 - 1)
	l = 2 ** 20 - 1
	s = 0
	for v in a:
		s += c[0] - loc(c, v)
		add(c, v)
	print(s)


def mcount(ar, left, right):
	(i, j, n) = (0, 0, 0)
	while i < len(left) or j < len(right):
		if i == len(left):
			ar[i + j] = right[j]
			j += 1
		elif j == len(right) or left[i] <= right[j]:
			ar[i + j] = left[i]
			i += 1
		else:
			ar[i + j] = right[j]
			j += 1
			n += len(left) - i
	return n

def sort(ar):
	if len(ar) <= 1:
		return 0
	left = ar[:(len(ar) + 1) // 2]
	right = ar[(len(ar) + 1) // 2:]
	return sort(left) + sort(right) + mcount(ar, left, right)
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	print(sort(ar))


import sys

def freopen(f, option, stream):
	import os
	oldf = open(f, option)
	oldfd = oldf.fileno()
	newfd = stream.fileno()
	os.close(newfd)
	os.dup2(oldfd, newfd)

def merge_sort(A):
	if len(A) <= 1:
		return (0, A)
	middle = len(A) // 2
	(left_inversions, left) = merge_sort(A[:middle])
	(right_inversions, right) = merge_sort(A[middle:])
	(merge_inversions, merged) = merge(left, right)
	inversions = left_inversions + right_inversions + merge_inversions
	return (inversions, merged)

def merge(left, right):
	result = []
	(i, j, inversions) = (0, 0, 0)
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			inversions += j
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	inversions += j * (len(left) - i)
	result += left[i:]
	result += right[j:]
	return (inversions, result)
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	angka = list(map(int, input().split()))
	(asd, ans) = merge_sort(angka)
	print(asd)


def mergesort(a):
	count = 0
	if len(a) <= 1:
		return (a, 0)
	middle = len(a) // 2
	left = a[:middle]
	right = a[middle:]
	(left, left_count) = mergesort(left)
	(right, right_count) = mergesort(right)
	count += left_count + right_count
	(result, merge_count) = merge(left, right)
	count += merge_count
	return (result, count)

def merge(left, right):
	result = []
	count = 0
	left_index = 0
	left_len = len(left)
	right_index = 0
	while left_index < len(left) and right_index < len(right):
		if left[left_index] <= right[right_index]:
			result.append(left[left_index])
			left_index += 1
			left_len -= 1
		else:
			count += left_len
			result.append(right[right_index])
			right_index += 1
	result = result + left[left_index:] + right[right_index:]
	return (result, count)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(mergesort(a)[1])


class BinartIndexedTree:

	def __init__(self, n):
		s = 1
		while n > s:
			s *= 2
		self.size = s
		self.data = list([0] * s)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i < self.size:
			self.data[i] += x
			i += i & -i

def inversions(arr):
	res = 0
	bit = BinartIndexedTree(max(arr) + 1)
	for (i, v) in enumerate(arr):
		res += i - bit.sum(v)
		bit.add(v, 1)
	return res

def main():
	for i in range(int(input())):
		n = input()
		print(inversions([int(x) for x in input().split()]))
main()


def merge(left, right):
	result = []
	(left_idx, right_idx, inv) = (0, 0, 0)
	while left_idx < len(left) and right_idx < len(right):
		if left[left_idx] <= right[right_idx]:
			result.append(left[left_idx])
			left_idx += 1
			inv += right_idx
		else:
			result.append(right[right_idx])
			right_idx += 1
	if left:
		result.extend(left[left_idx:])
	if right:
		result.extend(right[right_idx:])
	inv += right_idx * (len(left) - left_idx)
	return (inv, result)

def merge_sort(m):
	if len(m) <= 1:
		return (0, m)
	middle = len(m) // 2
	(inv_left, left) = merge_sort(m[:middle])
	(inv_right, right) = merge_sort(m[middle:])
	(inv_merged, merged) = merge(left, right)
	inversions = inv_left + inv_merged + inv_right
	return (inversions, merged)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(_) for _ in input().split()]
	(inv, merged) = merge_sort(a)
	print(inv)


def mergsort_inversion_count(a):
	if len(a) <= 1:
		return (a, 0)
	(a1, a2) = split(a)
	(a1_sorted, I1) = mergsort_inversion_count(a1)
	(a2_sorted, I2) = mergsort_inversion_count(a2)
	(a, I3) = merge_count_cross_inversions(a1_sorted, a2_sorted)
	return (a, I1 + I2 + I3)

def merge_count_cross_inversions(a1, a2):
	I = 0
	(i, j) = (0, 0)
	(n, m) = (len(a1), len(a2))
	a1.append(float('inf'))
	a2.append(float('inf'))
	a = []
	while i != n or j != m:
		if a1[i] <= a2[j]:
			a.append(a1[i])
			i += 1
		else:
			I += n - i
			a.append(a2[j])
			j += 1
	return (a, I)

def split(a):
	mid = len(a) // 2
	return (a[:mid], a[mid:])
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(ai) for ai in input().split()]
	(_, I) = mergsort_inversion_count(a)
	print(I)


RED = 'RED'
BLACK = 'BLACK'

class Tree:

	class Node:

		def __init__(self, key, color=None, size=1, left=None, right=None):
			self.key = key
			if color is None:
				color = RED
			self.color = color
			self.left = left
			self.right = right
			self.size = size

	def __init__(self):
		self.nil = Tree.Node(None, color=BLACK, size=0)
		self.root = self.nil

	def _rotate_left(self, h):
		x = h.right
		x_size = x.size
		x_size_left = x.left.size
		h.right = x.left
		x.left = h
		x.color = h.color
		h.color = RED
		x.size = h.size
		h.size = h.size - x_size + x_size_left
		return x

	def _rotate_right(self, h):
		x = h.left
		x_size = x.size
		x_size_right = x.right.size
		h.left = x.right
		x.right = h
		x.color = h.color
		h.color = RED
		x.size = h.size
		h.size = h.size - x_size + x_size_right
		return x

	def _flip_colors(self, h):
		h.color = RED
		h.left.color = BLACK
		h.right.color = BLACK

	def _put(self, h, key):
		if h == self.nil:
			return Tree.Node(key, left=self.nil, right=self.nil)
		h.size += 1
		if key < h.key:
			h.left = self._put(h.left, key)
		elif key > h.key:
			h.right = self._put(h.right, key)
		if h.right.color == RED and h.left.color == BLACK:
			h = self._rotate_left(h)
		if h.left.color == RED and h.left.left.color == RED:
			h = self._rotate_right(h)
		if h.left.color == RED and h.right.color == RED:
			self._flip_colors(h)
		return h

	def insert(self, key):
		self.root = self._put(self.root, key)
		self.root.color = BLACK

	def count_higher(self, key):
		return self._count(self.root, key)

	def _count(self, x, key):
		if x == self.nil:
			return 0
		if key == x.key:
			return x.right.size
		elif key > x.key:
			return self._count(x.right, key)
		else:
			all_left = self._count(x.left, key)
			left = x.left.size - all_left
			return x.size - left
T = int(input())

def is_sorted(A):
	for i in range(1, len(A)):
		if A[i - 1] > A[i]:
			return False
	return True
for _ in range(T):
	N = int(input())
	A = [int(c) for c in input().strip().split()]
	if is_sorted(A):
		print(0)
	else:
		c = 0
		tree = Tree()
		for a in A:
			c += tree.count_higher(a)
			tree.insert(a)
		print(c)


def mergeSort(arr):
	if len(arr) == 1:
		return (0, arr)
	mid = len(arr) // 2
	(cnt1, arr1) = mergeSort(arr[:mid])
	(cnt2, arr2) = mergeSort(arr[mid:])
	ret = []
	cnt = 0
	i = 0
	j = 0
	inx = 0
	while i < len(arr1) and j < len(arr2):
		if arr1[i] <= arr2[j]:
			ret.append(arr1[i])
			i += 1
		elif arr2[j] < arr1[i]:
			ret.append(arr2[j])
			cnt += len(arr1) - i
			j += 1
	while i < len(arr1):
		ret.append(arr1[i])
		i += 1
	while j < len(arr2):
		ret.append(arr2[j])
		cnt += len(arr1) - i
		j += 1
	return (cnt1 + cnt2 + cnt, ret)
T = int(input())
for _ in range(0, T):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]
	(cnt, _) = mergeSort(arr)
	print(cnt)


def mergeSort(alist):
	if len(alist) <= 1:
		return 0
	mid = len(alist) // 2
	lefthalf = alist[:mid]
	righthalf = alist[mid:]
	cnt = mergeSort(lefthalf)
	cnt += mergeSort(righthalf)
	i = 0
	j = 0
	k = 0
	while i < len(lefthalf) and j < len(righthalf):
		if lefthalf[i] <= righthalf[j]:
			alist[k] = lefthalf[i]
			i = i + 1
		else:
			cnt += len(lefthalf) - i
			alist[k] = righthalf[j]
			j = j + 1
		k = k + 1
	while i < len(lefthalf):
		alist[k] = lefthalf[i]
		i = i + 1
		k = k + 1
	while j < len(righthalf):
		alist[k] = righthalf[j]
		j = j + 1
		k = k + 1
	return cnt
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(mergeSort(arr))


def merge(A, p, q, r):
	i = j = k = inversions = 0
	n1 = q - p + 1
	n2 = r - q
	L = []
	R = []
	for i in range(n1):
		L.append(A[p + i])
	for j in range(n2):
		R.append(A[q + j + 1])
	i = j = 0
	for k in range(p, r + 1):
		if i == n1:
			A[k] = R[j]
			j += 1
		elif j == n2:
			A[k] = L[i]
			i += 1
		elif L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
			inversions += n1 - i
	return inversions

def merge_sort(A, p, r):
	if p < r:
		inversions = 0
		q = int((p + r) / 2)
		inversions += merge_sort(A, p, q)
		inversions += merge_sort(A, q + 1, r)
		inversions += merge(A, p, q, r)
		return inversions
	else:
		return 0
t = int(input().strip())
for _ in range(t):
	m = int(input().strip())
	ar = [int(i) for i in input().strip().split()]
	print(merge_sort(ar, 0, m - 1))


from bisect import bisect

def main():
	ncases = int(input())
	for _ in range(ncases):
		arrlen = int(input())
		arr = [int(f) for f in input().split()]
		assert len(arr) == arrlen
		print(swapcount(arr))

def swapcount(arr):
	if len(arr) <= 1:
		return 0
	half = len(arr) // 2
	count = swapcount(arr[:half]) + swapcount(arr[half:])
	base = sorted(arr[:half])
	count += sum((half - bisect(base, elt) for elt in arr[half:]))
	return count
main()


class NumGreaterTree:

	def __init__(self, n):
		self.n = n
		self.weight = 0
		self.leaf = n < 2
		if not self.leaf:
			self.half = n // 2
			self.left = NumGreaterTree(self.half)
			self.right = NumGreaterTree(self.n - self.half)

	def incr(self, i):
		self.weight += 1
		if not self.leaf:
			if i < self.half:
				self.left.incr(i)
			else:
				self.right.incr(i - self.half)

	def query(self, i):
		if self.leaf:
			if i == 0:
				return self.weight
			else:
				return 0
		elif i < self.half:
			return self.left.query(i) + self.right.weight
		else:
			return self.right.query(i - self.half)

	def __str__(self):
		return self.pretty()

	def pretty(self, tabs=0):
		string = ' ' * tabs + str(self.weight)
		if not self.leaf:
			string += '\n' + self.left.pretty(tabs + 2)
			string += '\n' + self.right.pretty(tabs + 2)
		return string

def countsort(arr):
	n = len(arr)
	sorted_arr = sorted(zip(arr, range(n)))
	count = 0
	tree = NumGreaterTree(n)
	for i in range(n):
		(x, j) = sorted_arr[i]
		count += tree.query(j)
		tree.incr(j)
	return count
for _ in range(int(input())):
	_ = input()
	arr = list(map(int, input().split()))
	print(countsort(arr))


import sys

def merge_count(ar, left, right):
	(i, j, n) = (0, 0, 0)
	while i < len(left) or j < len(right):
		if i == len(left):
			ar[i + j] = right[j]
			j += 1
		elif j == len(right) or left[i] <= right[j]:
			ar[i + j] = left[i]
			i += 1
		else:
			ar[i + j] = right[j]
			j += 1
			n += len(left) - i
	return n

def inversion_count(ar):
	if len(ar) <= 1:
		return 0
	left = ar[:(len(ar) + 1) // 2]
	right = ar[(len(ar) + 1) // 2:]
	return inversion_count(left) + inversion_count(right) + merge_count(ar, left, right)
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	ar = list(map(int, sys.stdin.readline().split()))
	print(inversion_count(ar))


class Sorter(object):

	def __init__(self, array):
		a = sum([x for (_, x) in self.mergesort([[i, 0] for i in array])])
		self.shifts = a

	def merge(self, l1, l2):
		result = []
		while len(l1) > 0 and len(l2) > 0:
			if l1[0][0] > l2[0][0]:
				item = l2.pop(0)
				item[1] += len(l1)
				result.append(item)
			else:
				result.append(l1.pop(0))
		result += l1 + l2
		return result

	def mergesort(self, w):
		if len(w) < 2:
			return w
		else:
			mid = len(w) // 2
			return self.merge(self.mergesort(w[:mid]), self.mergesort(w[mid:]))

def shifts_required(array):
	total = 0
	sorter = Sorter(array)
	return sorter.shifts
N = int(input())
for i in range(N):
	input()
	array = [int(a) for a in input().split()]
	print(shifts_required(array))


def merge(A, B):
	lengthA = len(A)
	lengthB = len(B)
	merged = []
	inversions = 0
	i = 0
	j = 0
	while i < lengthA and j < lengthB:
		if A[i] > B[j]:
			merged.append(B[j])
			inversions += lengthA - i
			j += 1
		else:
			merged.append(A[i])
			i += 1
	return (merged + A[i:] + B[j:], inversions)

def merge_sort(A):
	length = len(A)
	if length > 1:
		(A1, I1) = merge_sort(A[:length // 2])
		(A2, I2) = merge_sort(A[length // 2:])
		(AM, IM) = merge(A1, A2)
		return (AM, I1 + I2 + IM)
	else:
		return (A, 0)

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = [int(i) for i in input().split()]
		print(merge_sort(A)[1])
main()


def count_inversions(A, left, right):
	if left + 1 >= right:
		return 0
	midpoint = (left + right) // 2
	inv = 0
	inv += count_inversions(A, left, midpoint)
	inv += count_inversions(A, midpoint, right)
	inv += merge(A, left, midpoint, right)
	return inv

def merge(A, left, midpoint, right):
	inv = 0
	B = [None] * (right - left + 1)
	(i, j) = (left, midpoint)
	while i < midpoint and j < right:
		if A[i] <= A[j]:
			B[i - left + j - midpoint] = A[i]
			i += 1
		else:
			inv += midpoint - i
			B[i - left + j - midpoint] = A[j]
			j += 1
	if i < midpoint:
		B[i - left + j - midpoint:] = A[i:midpoint]
	else:
		B[i - left + j - midpoint:] = A[j:right]
	A[left:right] = B
	return inv

def main():
	T = int(input())
	for _ in range(T):
		n = int(input())
		A = [int(s) for s in input().split()]
		print(count_inversions(A, 0, len(A)))
main()


from array import array
from bisect import bisect
for _ in range(int(input())):
	N = int(input())
	s = array('i', [0])
	a = map(int, input().split())
	shifts = 0
	i = 0
	for x in a:
		if x < s[i]:
			j = bisect(s, x, 0, i)
			shifts += i - j + 1
			s.insert(j, x)
		else:
			s.append(x)
		i += 1
	print(shifts)


import array, bisect
T = input()
for t in range(int(T)):
	n = input()
	d = array.array('I', map(int, input().split()))
	dd = list(d)
	dd.sort()
	s = array.array('I', dd)
	c = 0
	for a in d:
		ind = bisect.bisect_left(s, a)
		c = c + ind
		s.pop(ind)
	print(c)


def merge_sort(A):
	lenA = len(A)
	if lenA <= 1:
		return (0, A)
	middle = lenA // 2
	(left_inversions, left) = merge_sort(A[:middle])
	(right_inversions, right) = merge_sort(A[middle:])
	(merge_inversions, merged) = merge(left, right)
	inversions = left_inversions + right_inversions + merge_inversions
	return (inversions, merged)

def merge(left, right):
	result = []
	lenL = len(left)
	lenR = len(right)
	(i, j, inversions) = (0, 0, 0)
	while i < lenL and j < lenR:
		if left[i] <= right[j]:
			inversions += j
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	inversions += j * (lenL - i)
	result += left[i:]
	result += right[j:]
	return (inversions, result)
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	ar = [int(x) for x in input().strip().split()]
	print(merge_sort(ar)[0])


def mergeSort(nums):
	length = len(nums)
	if length <= 1:
		return (nums, 0)
	mid = length // 2
	(left, countLeft) = mergeSort(nums[0:mid])
	(right, countRight) = mergeSort(nums[mid:length])
	countSum = countLeft + countRight
	indexRight = 0
	lengthRight = len(right)
	indexLeft = 0
	lengthLeft = len(left)
	merged = []
	while indexLeft < lengthLeft:
		if indexRight < lengthRight and left[indexLeft] > right[indexRight]:
			merged.append(right[indexRight])
			indexRight += 1
			countSum += lengthLeft - indexLeft
		else:
			merged.append(left[indexLeft])
			indexLeft += 1
	merged[lengthLeft + indexRight:] = right[indexRight:]
	return (merged, countSum)
testNum = int(input())
for _ in range(testNum):
	input()
	nums = [int(num) for num in input().split()]
	(array, count) = mergeSort(nums)
	print(count)


import bisect
import array
t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res = 0
	start = array.array('i', a[:1])
	for k in range(1, n):
		index = bisect.bisect_right(start, a[k])
		res += k - index
		start.insert(index, a[k])
	print(res)


case_number = int(input().strip())

def merge_sort(array):
	leng = len(array)
	if leng <= 1:
		return (array, 0)
	middle = int(leng / 2)
	left_part = array[:middle]
	right_part = array[middle:]
	(sorted_left, invertions_left) = merge_sort(left_part)
	(sorted_right, invertions_right) = merge_sort(right_part)
	(sorted_array, invertions) = merge(sorted_left, sorted_right)
	return (sorted_array, invertions_left + invertions + invertions_right)

def merge(left_array, right_array):
	invertions = 0
	i_index = 0
	j_index = 0
	leng_left = len(left_array)
	leng_right = len(right_array)
	merged_array = []
	while i_index < leng_left and j_index < leng_right:
		if left_array[i_index] <= right_array[j_index]:
			merged_array.append(left_array[i_index])
			i_index += 1
			invertions += j_index
		else:
			merged_array.append(right_array[j_index])
			j_index += 1
	invertions += j_index * (leng_left - i_index)
	merged_array += left_array[i_index:]
	merged_array += right_array[j_index:]
	return (merged_array, invertions)
for _ in range(case_number):
	arr_size = int(input().strip())
	array = [int(elem) for elem in input().strip().split(' ')]
	(array, invertions) = merge_sort(array)
	print(invertions)


from array import array
from bisect import bisect, insort

def count_shifts(arr):
	count = array('i', [arr[0]])
	total = 0
	length = len(count)
	for v in arr[1:]:
		p = bisect(count, v)
		if p != length:
			total += length - p
		insort(count, v)
		length += 1
	return total
t = int(input())
for _ in range(t):
	_ = input()
	arr = [int(x) for x in input().split()]
	print(count_shifts(arr))


from array import array
from bisect import bisect_right
t = int(input())
for _ in range(t):
	n = int(input())
	arr = array('I', [int(i) for i in input().split()])
	sarr = array('I', [arr[0]])
	result = 0
	for i in range(1, n):
		e = arr[i]
		j = bisect_right(sarr, e)
		sarr.insert(j, e)
		result += i - j
	print(result)


import bisect

def count_swaps(arr):

	def rec(unsorted_arr, sorted_arr):
		if sorted_arr[0] == sorted_arr[-1]:
			return 0
		mid = len(sorted_arr) // 2
		if sorted_arr[0] == sorted_arr[mid]:
			split = bisect.bisect_right(sorted_arr, sorted_arr[mid])
		else:
			split = bisect.bisect_left(sorted_arr, sorted_arr[mid])
		pivot = sorted_arr[split]
		shifts = 0
		count = 0
		left = []
		right = []
		for i in range(split):
			if unsorted_arr[i] >= pivot:
				count += 1
				shifts += split - i - 1
				right.append(unsorted_arr[i])
			else:
				left.append(unsorted_arr[i])
		for i in range(split, len(unsorted_arr)):
			if unsorted_arr[i] < pivot:
				shifts += i - split
				left.append(unsorted_arr[i])
			else:
				right.append(unsorted_arr[i])
		return shifts + count + rec(left, sorted_arr[:split]) + rec(right, sorted_arr[split:])
	return rec(arr, sorted(arr))

def main():
	for _ in range(int(input())):
		input()
		arr = [int(x) for x in input().split()]
		print(count_swaps(arr))
main()


import math

def merge(src, result, start, inc):
	end1 = start + inc
	end2 = min(start + 2 * inc, len(src))
	dist = 0
	(x, y, z) = (start, start + inc, start)
	while x < end1 and y < end2:
		if src[x] <= src[y]:
			result[z] = src[x]
			x += 1
		else:
			result[z] = src[y]
			dist += end1 - x
			y += 1
		z += 1
	if x < end1:
		result[z:end2] = src[x:end1]
	elif y < end2:
		result[z:end2] = src[y:end2]
	return dist

def merge_sort(S):
	n = len(S)
	logn = math.ceil(math.log(n, 2))
	(src, dest) = (S, [None] * n)
	dist = 0
	for i in (2 ** k for k in range(logn)):
		for j in range(0, n, 2 * i):
			dist += merge(src, dest, j, i)
		(src, dest) = (dest, src)
	if S is not src:
		S[0:n] = src[0:n]
	return dist
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	print(merge_sort(a))


def getInversions(arr, left, right):
	if left >= right:
		return 0
	mid = (left + right) // 2
	leftInversions = getInversions(arr, left, mid)
	rightInversions = getInversions(arr, mid + 1, right)
	mergeInversion = merge(arr, left, mid, right)
	return leftInversions + rightInversions + mergeInversion

def merge(arr, left, mid, right):
	leftLen = mid - left + 1
	rightLen = right - mid
	leftArr = arr[left:left + leftLen]
	rightArr = arr[mid + 1:mid + 1 + rightLen]
	i = 0
	j = 0
	k = left
	inversions = 0
	while i < leftLen and j < rightLen:
		if leftArr[i] <= rightArr[j]:
			arr[k] = leftArr[i]
			inversions += j
			i += 1
		else:
			arr[k] = rightArr[j]
			j += 1
		k += 1
	inversions += j * (leftLen - i)
	if i >= leftLen:
		while j < rightLen:
			arr[k] = rightArr[j]
			j += 1
			k += 1
	else:
		while i < leftLen:
			arr[k] = leftArr[i]
			i += 1
			k += 1
	return inversions

def solve(arr):
	return getInversions(arr, 0, len(arr) - 1)

def main():
	nrTests = int(input().strip())
	for _ in range(nrTests):
		input()
		arr = list(map(int, input().strip().split(' ')))
		count = solve(arr)
		print(count)
main()


TEMP = [0 for _ in range(100000)]
CUTOFF = 10

def insertion_sort(array, left, right):
	inversions = 0
	for i in range(left, right + 1):
		j = i
		while j > left and array[j] < array[j - 1]:
			(array[j], array[j - 1]) = (array[j - 1], array[j])
			inversions += 1
			j -= 1
	return inversions

def merge(array, temp, left, mid, right):
	(i, j) = (left, mid)
	inversions = 0
	for k in range(left, right + 1):
		if i > mid - 1:
			temp[k] = array[j]
			j += 1
		elif j > right:
			temp[k] = array[i]
			i += 1
		elif array[i] <= array[j]:
			temp[k] = array[i]
			i += 1
		else:
			temp[k] = array[j]
			j += 1
			inversions += mid - i
	array[left:right + 1] = temp[left:right + 1]
	return inversions

def merge_and_count(array, temp, lower, upper):
	invs = 0
	if upper - lower < CUTOFF:
		return insertion_sort(array, lower, upper)
	mid = (upper + lower) // 2
	invs = merge_and_count(array, temp, lower, mid)
	invs += merge_and_count(array, temp, mid + 1, upper)
	invs += merge(array, temp, lower, mid + 1, upper)
	return invs
for _ in range(int(input())):
	length = int(input())
	array = [int(x) for x in input().split()]
	print(merge_and_count(array, TEMP, 0, length - 1))


def merge_sort(arr, left, right):
	if left >= right:
		return 0
	ret = 0
	mid = (left + right) // 2
	ret += merge_sort(arr, left, mid)
	ret += merge_sort(arr, mid + 1, right)
	l = []
	(i, j) = (left, mid + 1)
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			l.append(arr[i])
			i += 1
		else:
			ret += mid - i + 1
			l.append(arr[j])
			j += 1
	if i <= mid:
		l += arr[i:mid + 1]
	if j <= right:
		l += arr[j:right + 1]
	arr[left:right + 1] = l[:]
	return ret
size = int(input().strip())
for i in range(size):
	input()
	l = [int(v) for v in input().strip().split()]
	print(merge_sort(l, 0, len(l) - 1))


def Div(data, start, end):
	if start == end:
		return 0
	if end - start == 1:
		if data[end] < data[start]:
			tmp = data[end]
			data[end] = data[start]
			data[start] = tmp
			return 1
		else:
			return 0
	p = 0
	lEnd = (end + start) // 2 - 1
	if lEnd - start > 0:
		p += Div(data, start, lEnd)
	if end - (lEnd + 1) > 0:
		p += Div(data, lEnd + 1, end)
	p += Mer(data, start, lEnd, end)
	return p

def Mer(data, start, lEnd, end):
	l = data[start:lEnd + 1]
	r = data[lEnd + 1:end + 1]
	lLen = len(l)
	rLen = len(r)
	lIndex = 0
	rIndex = 0
	p = 0
	while lIndex < lLen and rIndex < rLen:
		if l[lIndex] <= r[rIndex]:
			data[start] = l[lIndex]
			lIndex += 1
			p += rIndex
		else:
			data[start] = r[rIndex]
			rIndex += 1
		start += 1
	if lIndex < lLen:
		p += (lLen - lIndex) * rIndex
		while lIndex < lLen:
			data[start] = l[lIndex]
			start += 1
			lIndex += 1
	return p
for _ in range(int(input())):
	length = int(input())
	print(Div(list(map(int, input().split())), 0, length - 1))


def inversions_in(array, a, z):
	answer = 0
	if a < z:
		pivot = (a + z) // 2
		answer += inversions_in(array, a, pivot)
		answer += inversions_in(array, pivot + 1, z)
		answer += merge(array, a, z)
	return answer

def merge(array, a, z):
	inversions = 0
	pivot = (a + z) // 2
	left = array[a:pivot + 1]
	right = array[pivot + 1:z + 1]
	i = 0
	j = 0
	leftLen = len(left)
	rightLen = len(right)
	while i < leftLen and j < rightLen:
		if left[i] <= right[j]:
			array[a] = left[i]
			i += 1
			a += 1
		else:
			array[a] = right[j]
			inversions += leftLen - i
			j += 1
			a += 1
	while i < leftLen:
		array[a] = left[i]
		i += 1
		a += 1
	return inversions
T = int(input())
for _ in range(0, T):
	N = int(input())
	A = list(map(int, input().split()))
	answer = inversions_in(A, 0, len(A) - 1)
	print(answer)


def mergesort(arr, start, end):
	if start == end:
		return 0
	elif start == end - 1:
		if arr[start] > arr[end]:
			temp = arr[start]
			arr[start] = arr[end]
			arr[end] = temp
			return 1
		return 0
	mid = int(start + (end - start) / 2)
	swaps = mergesort(arr, start, mid)
	swaps += mergesort(arr, mid + 1, end)
	left = arr[start:mid + 1]
	right = arr[mid + 1:end + 1]
	left_len = len(left)
	right_len = len(right)
	left_ind = 0
	right_ind = 0
	curr = 0
	while left_ind < left_len and right_ind < right_len:
		if left[left_ind] <= right[right_ind]:
			arr[start + curr] = left[left_ind]
			left_ind += 1
		else:
			arr[start + curr] = right[right_ind]
			right_ind += 1
			swaps += left_len - left_ind
		curr += 1
	while left_ind < left_len:
		arr[start + curr] = left[left_ind]
		curr += 1
		left_ind += 1
	while right_ind < right_len:
		arr[start + curr] = right[right_ind]
		curr += 1
		right_ind += 1
	return swaps
T = int(input())
for k in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	print(mergesort(arr, 0, N - 1))


def merge_and_count(A1, A2):
	A = []
	(lA1, lA2) = (len(A1), len(A2))
	(count, i, j) = (0, 0, 0)
	while i < lA1 and j < lA2:
		if A1[i] <= A2[j]:
			A.append(A1[i])
			i += 1
		else:
			A.append(A2[j])
			count += len(A1) - i
			j += 1
	A += A1[i:] + A2[j:]
	return (A, count)

def sort_and_count(A):
	if len(A) == 1:
		return (A, 0)
	n = len(A) // 2
	(A1, A2) = (A[:n], A[n:])
	(A1, count_1) = sort_and_count(A1)
	(A2, count_2) = sort_and_count(A2)
	(A, count_m) = merge_and_count(A1, A2)
	return (A, count_1 + count_2 + count_m)
T = int(input().strip())
for _ in range(T):
	_ = input()
	L = list(map(int, input().strip().split()))
	(_, i) = sort_and_count(L)
	print(i)


from bisect import bisect
from array import array
for _ in range(int(input())):
	N = int(input())
	a = array('I', map(int, input().split()))
	s_a = array('I', [a[0]])
	shifts = 0
	for i in range(1, N):
		value = a[i]
		insert_index = bisect(s_a, value)
		s_a.insert(insert_index, value)
		shifts += i - insert_index
	print(shifts)


def mergeCount(lst, length):
	if length < 2:
		return 0
	left = lst[0:int(length / 2)]
	right = lst[int(length / 2):length]
	len_left = int(length / 2)
	len_right = len(right)
	swaps = 0
	swaps += mergeCount(left, len_left)
	swaps += mergeCount(right, len_right)
	i = 0
	j = 0
	ind = 0
	while i < len_left and j < len_right:
		if left[i] > right[j]:
			swaps += len_left - i
			lst[ind] = right[j]
			j += 1
		else:
			lst[ind] = left[i]
			i += 1
		ind += 1
	while i < len_left:
		lst[ind] = left[i]
		i += 1
		ind += 1
	while j < len_right:
		lst[ind] = right[j]
		j += 1
		ind += 1
	return swaps
cases = int(input().strip())
for c in range(cases):
	length = int(input().strip())
	array = [int(x) for x in input().strip().split()]
	print(mergeCount(array, length))


from random import randrange

def count_shifts(A):
	shifts = 0
	if len(A) > 1:
		bigger_count = 0
		equal_count = 0
		L = []
		R = []
		p = A[randrange(0, len(A))]
		for a in A:
			if a > p:
				bigger_count += 1
				R.append(a)
			elif a == p:
				equal_count += 1
				shifts += bigger_count
			else:
				shifts += bigger_count + equal_count
				L.append(a)
		shifts += count_shifts(L)
		shifts += count_shifts(R)
	return shifts
T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	A = [int(s) for s in input().strip().split(' ')]
	print(count_shifts(A))


import sys
V = int(input().strip())
arl = []
ars = []
for i in range(V):
	arl.append(int(input().strip()))
	ars.append(list(map(int, input().strip().split(' '))))

def merge_sort(A):
	if len(A) <= 1:
		return (0, A)
	middle = int(len(A) / 2)
	(left_inversions, left) = merge_sort(A[:middle])
	(right_inversions, right) = merge_sort(A[middle:])
	(merge_inversions, merged) = merge(left, right)
	inversions = left_inversions + right_inversions + merge_inversions
	return (inversions, merged)

def merge(left, right):
	result = []
	(i, j, inversions) = (0, 0, 0)
	lleft = len(left)
	lright = len(right)
	while i < lleft and j < lright:
		if left[i] <= right[j]:
			inversions += j
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	inversions += j * (lleft - i)
	result += left[i:]
	result += right[j:]
	return (inversions, result)
for i in range(len(arl)):
	s = merge_sort(ars[i])
	print(s[0])


def inv_merge_sort(x):
	if len(x) < 2:
		return (x, 0)
	else:
		(x1, i1) = inv_merge_sort(x[:len(x) // 2])
		(x2, i2) = inv_merge_sort(x[len(x) // 2:])
		sort = []
		invs = i1 + i2
		while x1 and x2:
			if x1[-1] <= x2[-1]:
				sort.append(x2.pop())
			else:
				sort.append(x1.pop())
				invs += len(x2)
		sort.extend(x1[::-1])
		sort.extend(x2[::-1])
		return (sort[::-1], invs)
t = int(input())
for _ in range(t):
	input()
	x = list(map(int, input().split()))
	(_, invs) = inv_merge_sort(x)
	print(invs)