Given an array arr[] of size N of non negative integers. We can perform a swap operation on any two adjacent elements in the array. The task is to find the minimum number of swaps needed to sort the array in non - decreasing order. 
 
Example 1: 
Input:
N = 4
arr[] = {4, 1, 2, 3}
Output: 3
Explanation: (4,1,2,3) -> (1,4,2,3) -> 
(1,2,4,3) -> (1,2,3,4). Hence we need 
a total of 3 swaps to sort it in 
non - decreasing order.
Ã¢â¬â¹Example 2: 
Input: 
N = 4
arr[] = {4, 4, 2, 3}
Output: 4
Explanation: (4,4,2,3) -> (4,2,4,3) ->
(4,2,3,4) -> (2,4,3,4) -> (2,3,4,4,).
Hence we need a total of 4 swap to 
sort it in increasing order.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countSwaps() which takes the array arr[] and N as inputs and returns the minimum number of swaps needed to sort the array in non - decreasing order.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ arr[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #User function Template for python3
class Solution:
	def countSwaps(self, arr, n):
		# code here

Solutions:
class Solution:

	def merge(self, arr, mid, l, r):
		n1 = mid - l + 1
		n2 = r - mid
		left = []
		right = []
		for i in range(n1):
			left.append(arr[l + i])
		for i in range(n2):
			right.append(arr[mid + 1 + i])
		count = 0
		i = 0
		k = l
		j = 0
		while i < n1 and j < n2:
			if left[i] <= right[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = right[j]
				j += 1
				count += n1 - i
			k += 1
		while i < n1:
			arr[k] = left[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = right[j]
			j += 1
			k += 1
		return count

	def mergeSort(self, arr, l, r):
		count = 0
		if l < r:
			mid = (l + r) // 2
			count += self.mergeSort(arr, l, mid)
			count += self.mergeSort(arr, mid + 1, r)
			count += self.merge(arr, mid, l, r)
		return count

	def countSwaps(self, arr, n):
		return self.mergeSort(arr, 0, n - 1)


class Solution:

	def countSwaps(self, arr, n):

		def merge_sort(arr, l, r):
			res = 0
			if l < r:
				m = (l + r) // 2
				res += merge_sort(arr, l, m)
				res += merge_sort(arr, m + 1, r)
				res += merge(arr, l, m, r)
			return res

		def merge(arr, l, m, r):
			(n1, n2) = (m - l + 1, r - m)
			(L, R) = ([], [])
			for i in range(n1):
				L.append(arr[l + i])
			for j in range(n2):
				R.append(arr[m + 1 + j])
			(i, j, k, res) = (0, 0, l, 0)
			while i < n1 and j < n2:
				if L[i] <= R[j]:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
					res += n1 - i
				k += 1
			while i < n1:
				arr[k] = L[i]
				i += 1
				k += 1
			while j < n2:
				arr[k] = R[j]
				j += 1
				k += 1
			return res
		return merge_sort(arr, 0, n - 1)


class Solution:

	def merge(self, arr, l, mid, r):
		a = arr[l:mid + 1]
		b = arr[mid + 1:r + 1]
		k = l
		i = 0
		j = 0
		inv = 0
		n = len(a)
		m = len(b)
		while i < n and j < m:
			if a[i] <= b[j]:
				arr[k] = a[i]
				i += 1
				k += 1
			else:
				arr[k] = b[j]
				inv += n - i
				k += 1
				j += 1
		while i < n:
			arr[k] = a[i]
			i += 1
			k += 1
		while j < m:
			arr[k] = b[j]
			j += 1
			k += 1
		return inv

	def mergesort(self, arr, l, r):
		inv = 0
		if l < r:
			mid = (l + r) // 2
			inv += self.mergesort(arr, l, mid)
			inv += self.mergesort(arr, mid + 1, r)
			inv += self.merge(arr, l, mid, r)
		return inv

	def countSwaps(self, arr, n):
		return self.mergesort(arr, 0, n - 1)


class Solution:

	def countSwaps(self, arr, n):
		ans = [0]

		def merge(l, r):
			(p, q) = (0, 0)
			marr = [0] * (len(l) + len(r))
			while p < len(l) and q < len(r):
				if l[p] <= r[q]:
					marr[p + q] = l[p]
					p += 1
				else:
					ans[0] += len(l) - p
					marr[p + q] = r[q]
					q += 1
			while p < len(l):
				marr[p + q] = l[p]
				p += 1
			while q < len(r):
				marr[p + q] = r[q]
				q += 1
			return marr

		def mergeSort(arr):
			if len(arr) <= 1:
				return arr
			mid = (len(arr) + 1) // 2
			(l, r) = (arr[:mid], arr[mid:])
			return merge(mergeSort(l), mergeSort(r))
		mergeSort(arr)
		return ans[0]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.countSwaps(arr, n)
		print(ans)


class Solution:

	def countSwaps(self, arr, n):

		def inversion(arr, temp, start, end):
			if start >= end:
				return 0
			mid = (start + end) // 2
			l = inversion(arr, temp, start, mid)
			r = inversion(arr, temp, mid + 1, end)
			m = merge(arr, temp, start, mid, end)
			return l + r + m

		def merge(arr, temp, start, mid, end):
			k = start
			i = start
			j = mid + 1
			cnt = 0
			while i <= mid and j <= end:
				if arr[i] > arr[j]:
					temp[k] = arr[j]
					j += 1
					k += 1
					cnt += mid - i + 1
				else:
					temp[k] = arr[i]
					i += 1
					k += 1
			while i <= mid:
				temp[k] = arr[i]
				k += 1
				i += 1
			while j <= end:
				temp[k] = arr[j]
				k += 1
				j += 1
			for v in range(start, end + 1):
				arr[v] = temp[v]
			return cnt
		temp = [0] * n
		return inversion(arr, temp, 0, n - 1)


class Solution:

	def countSwaps(self, arr, n):
		return self.merge_sort(arr, [0] * n, 0, n - 1)

	def merge_sort(self, arr, temp, low, high):
		if low == high:
			return 0
		mid = low + (high - low) // 2
		left = self.merge_sort(arr, temp, low, mid)
		right = self.merge_sort(arr, temp, mid + 1, high)
		ans = self.merge(arr, temp, low, mid, mid + 1, high)
		return ans + left + right

	def merge(self, arr, temp, l1, r1, l2, r2):
		(i, j, k) = (l1, l2, 0)
		inversions = 0
		while i <= r1 and j <= r2:
			if arr[i] <= arr[j]:
				temp[k] = arr[i]
				i += 1
			else:
				temp[k] = arr[j]
				j += 1
				inversions += r1 - i + 1
			k += 1
		while i <= r1:
			temp[k] = arr[i]
			i += 1
			k += 1
		while j <= r2:
			temp[k] = arr[j]
			j += 1
			k += 1
		for i in range(l1, r2 + 1):
			arr[i] = temp[i - l1]
		return inversions


def solve(arr):
	if len(arr) <= 1:
		return 0
	mid = len(arr) // 2
	left = arr[:mid]
	right = arr[mid:]
	count = 0
	count += solve(left)
	count += solve(right)
	(i, j, k) = (0, 0, 0)
	while i < len(left) and j < len(right):
		if left[i] > right[j]:
			count += len(left) - i
			arr[k] = right[j]
			j += 1
		else:
			arr[k] = left[i]
			i += 1
		k += 1
	while i < len(left):
		arr[k] = left[i]
		i += 1
		k += 1
	while j < len(right):
		arr[k] = right[j]
		j += 1
		k += 1
	return count

class Solution:

	def countSwaps(self, arr, n):
		return solve(arr)