Given an array of integers. Find the Inversion Count in the array. 
Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum. 
Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.
 
Example 1:
Input: N = 5, arr[] = {2, 4, 1, 3, 5}
Output: 3
Explanation: The sequence 2, 4, 1, 3, 5 
has three inversions (2, 1), (4, 1), (4, 3).
Example 2:
Input: N = 5
arr[] = {2, 3, 4, 5, 6}
Output: 0
Explanation: As the sequence is already 
sorted so there is no inversion count.
Example 3:
Input: N = 3, arr[] = {10, 10, 10}
Output: 0
Explanation: As all the elements of array 
are same, so there is no inversion count.
Your Task:
You don't need to read input or print anything. Your task is to complete the function inversionCount() which takes the array arr[] and the size of the array as inputs and returns the inversion count of the given array.
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 5*10^{5}
1 ≤ arr[i] ≤ 10^{18}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Divide and conquer

Starter code: class Solution:
    #User function Template for python3
    
    # arr[]: Input Array
    # N : Size of the Array arr[]
    #Function to count inversions in the array.
    def inversionCount(self, arr, n):
        # Your Code Here

Solutions:
class Solution:

	def merge(self, start, mid, end, arr):
		(len1, len2) = (mid - start + 1, end - mid)
		arr1 = [arr[ind] for ind in range(start, mid + 1)]
		arr2 = [arr[ind] for ind in range(mid + 1, end + 1)]
		(i, j, k) = (0, 0, start)
		count = 0
		while i < len1 and j < len2:
			if arr1[i] <= arr2[j]:
				arr[k] = arr1[i]
				i += 1
			else:
				arr[k] = arr2[j]
				count += len1 - i
				j += 1
			k += 1
		while i < len1:
			arr[k] = arr1[i]
			i += 1
			k += 1
		while j < len2:
			arr[k] = arr2[j]
			j += 1
			k += 1
		return count

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

	def inversionCount(self, nums, n):
		return self.mergeSort(0, n - 1, nums)


class Solution:

	def inversionCount(self, arr, n):
		inversion_count = [0]
		self.mergeSort(arr, 0, n - 1, inversion_count)
		return inversion_count[0]

	def mergeSort(self, arr, left, right, inversion_count):
		if left < right:
			mid = (left + right) // 2
			self.mergeSort(arr, left, mid, inversion_count)
			self.mergeSort(arr, mid + 1, right, inversion_count)
			self.merge(arr, left, mid, right, inversion_count)

	def merge(self, arr, left, mid, right, inversion_count):
		left_temp = arr[left:mid + 1]
		right_temp = arr[mid + 1:right + 1]
		i = j = 0
		k = left
		while i < len(left_temp) and j < len(right_temp):
			if left_temp[i] <= right_temp[j]:
				arr[k] = left_temp[i]
				i += 1
			else:
				arr[k] = right_temp[j]
				j += 1
				inversion_count[0] += mid - left + 1 - i
			k += 1
		while i < len(left_temp):
			arr[k] = left_temp[i]
			i += 1
			k += 1
		while j < len(right_temp):
			arr[k] = right_temp[j]
			j += 1
			k += 1


class Solution:

	def inversionCount(self, arr, n):
		return self.helper(arr, 0, n - 1)

	def helper(self, arr, left, right):
		inversion = 0
		if left < right:
			mid = left + (right - left) // 2
			inversion += self.helper(arr, left, mid)
			inversion += self.helper(arr, mid + 1, right)
			inversion += self.merge(arr, left, right, mid)
		return inversion

	def merge(self, arr, l, r, mid):
		left = arr[l:mid + 1]
		right = arr[mid + 1:r + 1]
		left_len = len(left)
		right_len = len(right)
		inversion = 0
		(i, j, k) = (0, 0, l)
		while i < left_len and j < right_len:
			if left[i] <= right[j]:
				arr[k] = left[i]
				i += 1
				k += 1
			else:
				inversion += left_len - i
				arr[k] = right[j]
				j += 1
				k += 1
		while i < left_len:
			arr[k] = left[i]
			i += 1
			k += 1
		while j < right_len:
			arr[k] = right[j]
			j += 1
			k += 1
		return inversion


class Solution:

	def inversionCount(self, arr, n):
		count = 0

		def merge(arr, low, mid, high):
			count = 0
			temp = []
			left = low
			right = mid + 1
			while left <= mid and right <= high:
				if arr[left] <= arr[right]:
					temp.append(arr[left])
					left += 1
				else:
					count += mid - left + 1
					temp.append(arr[right])
					right += 1
			while left <= mid:
				temp.append(arr[left])
				left += 1
			while right <= high:
				temp.append(arr[right])
				right += 1
			for i in range(low, high + 1, 1):
				arr[i] = temp[i - low]
			return count

		def mergesort(arr, low, high):
			mid = (low + high) // 2
			count = 0
			if low >= high:
				return count
			count += mergesort(arr, low, mid)
			count += mergesort(arr, mid + 1, high)
			count += merge(arr, low, mid, high)
			return count
		count = mergesort(arr, 0, len(arr) - 1)
		return count


class Solution:

	def inversionCount(self, arr, n):

		def merge_sort(arr, left, right):
			count = 0
			if left < right:
				mid = (left + right) // 2
				count += merge_sort(arr, left, mid)
				count += merge_sort(arr, mid + 1, right)
				count += merge(arr, left, right, mid)
			return count

		def merge(arr, left, right, mid):
			count = 0
			i = left
			j = mid + 1
			temp = []
			while i <= mid and j <= right:
				if arr[i] <= arr[j]:
					temp.append(arr[i])
					i += 1
				else:
					count += mid - i + 1
					temp.append(arr[j])
					j += 1
			while i <= mid:
				temp.append(arr[i])
				i += 1
			while j <= right:
				temp.append(arr[j])
				j += 1
			for i in range(len(temp)):
				arr[left + i] = temp[i]
			return count
		return merge_sort(arr, 0, n - 1)


class Solution:

	def inversionCount(self, arr, n):

		def merge(arr, temp, left, mid, right):
			inv_count = 0
			i = left
			j = mid
			k = left
			while i <= mid - 1 and j <= right:
				if arr[i] <= arr[j]:
					temp[k] = arr[i]
					k += 1
					i += 1
				else:
					temp[k] = arr[j]
					k += 1
					j += 1
					inv_count += mid - i
			while i <= mid - 1:
				temp[k] = arr[i]
				k += 1
				i += 1
			while j <= right:
				temp[k] = arr[j]
				k += 1
				j += 1
			for i in range(left, right + 1):
				arr[i] = temp[i]
			return inv_count

		def merge_sort(arr, temp, left, right):
			inv_count = 0
			if right > left:
				mid = (left + right) // 2
				inv_count += merge_sort(arr, temp, left, mid)
				inv_count += merge_sort(arr, temp, mid + 1, right)
				inv_count += merge(arr, temp, left, mid + 1, right)
			return inv_count
		temp = [0] * n
		return merge_sort(arr, temp, 0, n - 1)


class Solution:
	overall = 0

	def msort(self, arr):
		n = len(arr)
		if n == 1:
			return arr
		else:
			split_point = n // 2
			left = self.msort(arr[:split_point])
			right = self.msort(arr[split_point:])
			lenght_l = len(left)
			lenght_r = len(right)
			(i, j) = (0, 0)
			res = []
			while i < lenght_l and j < lenght_r:
				if left[i] <= right[j]:
					res.append(left[i])
					i += 1
				else:
					res.append(right[j])
					self.overall += lenght_l - i
					j += 1
			if i < lenght_l:
				res += left[i:]
			elif j < lenght_r:
				res += right[j:]
			return res

	def inversionCount(self, arr, n):
		self.msort(arr)
		return self.overall


class Solution:

	def inversionCount(self, arr, n):
		inversion_count = 0
		(arr, inversion_count) = self.mergeSort(arr, inversion_count)
		return inversion_count

	def mergeSort(self, arr, inversion_count):
		if len(arr) <= 1:
			return (arr, inversion_count)
		mid = len(arr) // 2
		left = arr[:mid]
		right = arr[mid:]
		(left, inversion_count) = self.mergeSort(left, inversion_count)
		(right, inversion_count) = self.mergeSort(right, inversion_count)
		(arr, inversion_count) = self.merge(left, right, inversion_count)
		return (arr, inversion_count)

	def merge(self, left, right, inversion_count):
		merged = []
		i = j = 0
		while i < len(left) and j < len(right):
			if left[i] <= right[j]:
				merged.append(left[i])
				i += 1
			else:
				merged.append(right[j])
				inversion_count += len(left) - i
				j += 1
		merged.extend(left[i:])
		merged.extend(right[j:])
		return (merged, inversion_count)


class Solution:

	def splitter(self, arr, left, right, temp):
		if left >= right - 1:
			return 0
		mid = (right + left) // 2
		count = 0
		count += self.splitter(arr, left, mid, temp)
		count += self.splitter(arr, mid, right, temp)
		count += self.merger(arr, left, mid, right, temp)
		return count

	def merger(self, arr, left, mid, right, temp):
		count = 0
		i = left
		j = mid
		ind = left
		while i < mid and j < right:
			if arr[i] <= arr[j]:
				temp[ind] = arr[i]
				ind += 1
				i += 1
			else:
				temp[ind] = arr[j]
				count += mid - i
				ind += 1
				j += 1
		while i < mid:
			temp[ind] = arr[i]
			i += 1
			ind += 1
		while j < right:
			temp[ind] = arr[j]
			j += 1
			ind += 1
		for i in range(left, right):
			arr[i] = temp[i]
		return count

	def inversionCount(self, arr, n):
		temp = [-1 for i in range(n)]
		return self.splitter(arr, 0, n, temp)


class Solution:

	def mergeSortHelper(self, arr):
		total = 0
		if len(arr) > 1:
			mid = len(arr) // 2
			L = arr[:mid]
			R = arr[mid:]
			total += self.mergeSortHelper(L)
			total += self.mergeSortHelper(R)
			j = 0
			for i in range(len(L)):
				while j < len(R) and L[i] > R[j]:
					j += 1
				total += j
			i = 0
			j = 0
			k = 0
			while i < len(L) and j < len(R):
				if L[i] <= R[j]:
					arr[k] = L[i]
					i += 1
					k += 1
				else:
					arr[k] = R[j]
					j += 1
					k += 1
			while i < len(L):
				arr[k] = L[i]
				i += 1
				k += 1
			while j < len(R):
				arr[k] = R[j]
				j += 1
				k += 1
		return total

	def mergeSortHelperNew(self, arr):
		total = 0
		if len(arr) > 1:
			mid = len(arr) // 2
			L = arr[:mid]
			R = arr[mid:]
			n = len(L)
			m = len(R)
			total += self.mergeSortHelperNew(L)
			total += self.mergeSortHelperNew(R)
			j = 0
			for i in range(n):
				while j < m and L[i] > R[j]:
					j += 1
				total += j
			i = 0
			j = 0
			k = 0
			while i < n and j < m:
				if L[i] <= R[j]:
					arr[k] = L[i]
					i += 1
					k += 1
				else:
					arr[k] = R[j]
					j += 1
					k += 1
			while i < n:
				arr[k] = L[i]
				i += 1
				k += 1
			while j < m:
				arr[k] = R[j]
				j += 1
				k += 1
		return total

	def inversionCount(self, arr, n):
		return self.mergeSortHelperNew(arr)


class Solution:
	inversion_count = 0

	def inversionCount(self, a, n):
		global inversion_count
		inversion_count = 0
		self.merge_sort(a, 0, n - 1)
		return inversion_count

	def merge(self, a, start, mid, end):
		global inversion_count
		temp = [0 for i in range(end - start + 1)]
		(i, j, k) = (start, mid + 1, 0)
		while i <= mid and j <= end:
			if a[i] <= a[j]:
				temp[k] = a[i]
				k += 1
				i += 1
			else:
				temp[k] = a[j]
				k += 1
				j += 1
				inversion_count += mid - i + 1
		while i <= mid:
			temp[k] = a[i]
			k += 1
			i += 1
		while j <= end:
			temp[k] = a[j]
			k += 1
			j += 1
		for i in range(start, end + 1):
			a[i] = temp[i - start]

	def merge_sort(self, a, start, end):
		if start < end:
			mid = (start + end) // 2
			self.merge_sort(a, start, mid)
			self.merge_sort(a, mid + 1, end)
			self.merge(a, start, mid, end)


class Solution:

	def inversionCount(self, arr, n):
		return self.mergeSort(arr, n)

	def mergeSort(self, arr, n):
		if n < 2:
			return 0
		mid = n // 2
		left = arr[:mid]
		right = arr[mid:]
		c = 0
		c += self.mergeSort(left, mid)
		c += self.mergeSort(right, n - mid)
		c += self.merge(arr, left, right, mid, n - mid)
		return c

	def merge(self, arr, left, right, mid, n):
		i = j = k = c = 0
		while i < mid and j < n:
			if left[i] <= right[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = right[j]
				c += mid - i
				j += 1
			k += 1
		while i < mid:
			arr[k] = left[i]
			i += 1
			k += 1
		while j < n:
			arr[k] = right[j]
			j += 1
			k += 1
		return c


class Solution:
	ans = 0

	def merge(self, arr, l, mid, r):
		arr1 = arr[l:mid + 1]
		arr2 = arr[mid + 1:r + 1]
		i = 0
		j = 0
		k = l
		while i < len(arr1) and j < len(arr2):
			if arr1[i] <= arr2[j]:
				arr[k] = arr1[i]
				k += 1
				i += 1
			else:
				arr[k] = arr2[j]
				k += 1
				j += 1
				self.ans += mid - (l + i) + 1
		while i < len(arr1):
			arr[k] = arr1[i]
			i += 1
			k += 1
		while j < len(arr2):
			arr[k] = arr2[j]
			j += 1
			k += 1

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

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


class Solution:

	def inversionMerge(self, arr, l, m, h):
		left = arr[l:m + 1]
		right = arr[m + 1:h + 1]
		(i, j, res, k) = (0, 0, 0, l)
		while i < len(left) and j < len(right):
			if left[i] <= right[j]:
				arr[k] = left[i]
				k += 1
				i += 1
			else:
				arr[k] = right[j]
				k += 1
				j += 1
				res += len(left) - i
		while i < len(left):
			arr[k] = left[i]
			k += 1
			i += 1
		while j < len(right):
			arr[k] = right[j]
			k += 1
			j += 1
		return res

	def inversionCountHelper(self, arr, l, h):
		res = 0
		if l < h:
			m = (l + h) // 2
			res += self.inversionCountHelper(arr, l, m)
			res += self.inversionCountHelper(arr, m + 1, h)
			res += self.inversionMerge(arr, l, m, h)
		return res

	def inversionCount(self, arr, n):
		return self.inversionCountHelper(arr, 0, n - 1)


class Solution:

	def inversionCount(self, arr, n):
		l = 0
		r = len(arr) - 1
		x = self.mergeSort(arr, l, r)
		return x

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

	def merge(self, arr, l, m, r):
		left = arr[l:m + 1]
		right = arr[m + 1:r + 1]
		res = i = j = 0
		k = l
		while i < len(left) and j < len(right):
			if left[i] <= right[j]:
				arr[k] = left[i]
				i += 1
				k += 1
			else:
				arr[k] = right[j]
				res += len(left) - i
				j += 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 res


class Solution:

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

	def mergesort(self, arr, l, r):
		res = 0
		if r > l:
			m = (l + r) // 2
			res += self.mergesort(arr, l, m)
			res += self.mergesort(arr, m + 1, r)
			res += self.count_merge(arr, l, m, r)
		return res

	def count_merge(self, a, low, mid, high):
		left = a[low:mid + 1]
		right = a[mid + 1:high + 1]
		k = low
		i = 0
		j = 0
		res = 0
		while i < len(left) and j < len(right):
			if left[i] <= right[j]:
				a[k] = left[i]
				i += 1
				k += 1
			else:
				a[k] = right[j]
				j += 1
				k += 1
				res += len(left) - i
		while i < len(left):
			a[k] = left[i]
			i += 1
			k += 1
		while j < len(right):
			a[k] = right[j]
			j += 1
			k += 1
		return res


def checkInvetion(arr):
	totalAns = 0

	def inversionCount(arr):
		nonlocal totalAns
		if len(arr) <= 1:
			return totalAns
		size = len(arr)
		left = arr[:size // 2]
		right = arr[size // 2:]
		inversionCount(left)
		inversionCount(right)
		numI = len(left)
		numJ = len(right)
		numK = len(arr)
		(i, j, k) = (0, 0, 0)
		while i < numI and j < numJ:
			if left[i] > right[j]:
				totalAns += numI - i
			a = 0
			if left[i] > right[j]:
				arr[k] = right[j]
				j += 1
			else:
				arr[k] = left[i]
				i += 1
			k += 1
		while i < numI:
			arr[k] = left[i]
			i += 1
			k += 1
		while j < numJ:
			arr[k] = right[j]
			j += 1
			k += 1
		return totalAns
	return inversionCount(arr)

class Solution:

	def inversionCount(self, arr, n):
		return checkInvetion(arr)


class Solution:

	def merge(self, arr, temp, left, mid, right):
		inv_count = 0
		i = left
		j = mid
		k = left
		while i <= mid - 1 and j <= right:
			if arr[i] <= arr[j]:
				temp[k] = arr[i]
				k += 1
				i += 1
			else:
				temp[k] = arr[j]
				k += 1
				j += 1
				inv_count += mid - i
		while i <= mid - 1:
			temp[k] = arr[i]
			k += 1
			i += 1
		while j <= right:
			temp[k] = arr[j]
			k += 1
			j += 1
		for i in range(left, right + 1):
			arr[i] = temp[i]
		return inv_count

	def mergeSort(self, arr, temp, low, high):
		inv_count = 0
		if high > low:
			mid = (low + high) // 2
			inv_count += self.mergeSort(arr, temp, low, mid)
			inv_count += self.mergeSort(arr, temp, mid + 1, high)
			inv_count += self.merge(arr, temp, low, mid + 1, high)
		return inv_count

	def inversionCount(self, arr, n):
		temp = [0] * n
		ans = self.mergeSort(arr, temp, 0, n - 1)
		return ans


class Solution:

	def inversionCount(self, arr, n):

		def merge(arr, left, mid, right):
			temp = []
			i = left
			j = mid + 1
			cnt = 0
			while i <= mid and j <= right:
				if arr[i] > arr[j]:
					temp.append(arr[j])
					cnt += mid - i + 1
					j += 1
				else:
					temp.append(arr[i])
					i += 1
			while i <= mid:
				temp.append(arr[i])
				i += 1
			while j <= right:
				temp.append(arr[j])
				j += 1
			for k in range(left, right + 1):
				arr[k] = temp[k - left]
			return cnt

		def mergeSort(arr, left, right):
			cnt = 0
			if left >= right:
				return cnt
			mid = (left + right) // 2
			cnt += mergeSort(arr, left, mid)
			cnt += mergeSort(arr, mid + 1, right)
			cnt += merge(arr, left, mid, right)
			return cnt
		return mergeSort(arr, 0, len(arr) - 1)


def merge(arr, low, mid, high):
	i = low
	j = mid + 1
	temp = []
	cnt = 0
	while i <= mid and j <= high:
		if arr[i] > arr[j]:
			temp.append(arr[j])
			cnt += mid - i + 1
			j += 1
		else:
			temp.append(arr[i])
			i += 1
	while i <= mid:
		temp.append(arr[i])
		i += 1
	while j <= high:
		temp.append(arr[j])
		j += 1
	for k in range(low, high + 1):
		arr[k] = temp[k - low]
	return cnt

def divide(arr, low, high):
	cnt = 0
	if low >= high:
		return cnt
	mid = (low + high) // 2
	cnt += divide(arr, low, mid)
	cnt += divide(arr, mid + 1, high)
	cnt += merge(arr, low, mid, high)
	return cnt

class Solution:

	def inversionCount(self, arr, n):
		return divide(arr, 0, n - 1)


class Solution:

	def inversionCount(self, arr, n):
		count = 0

		def solve(left, right):
			if left == right:
				return
			else:
				mid = (left + right) // 2
				solve(left, mid)
				solve(mid + 1, right)
				p1 = left
				p2 = mid + 1
				while p1 <= mid and p2 <= right:
					if arr[p1] > arr[p2]:
						nonlocal count
						count += mid - p1 + 1
						p2 += 1
					else:
						p1 += 1
				temp = []
				p1 = left
				p2 = mid + 1
				while p1 <= mid and p2 <= right:
					if arr[p1] <= arr[p2]:
						temp.append(arr[p1])
						p1 += 1
					else:
						temp.append(arr[p2])
						p2 += 1
				while p1 <= mid:
					temp.append(arr[p1])
					p1 += 1
				while p2 <= right:
					temp.append(arr[p2])
					p2 += 1
				for i in range(left, right + 1):
					arr[i] = temp[i - left]
		solve(0, len(arr) - 1)
		return count


class Solution:

	def inversionCount(self, arr, n):
		if n <= 1:
			return 0
		mid = len(arr) // 2
		left = arr[:mid]
		right = arr[mid:]
		count = self.inversionCount(left, len(left)) + self.inversionCount(right, len(right))
		i = j = k = 0
		while i < len(left) and j < len(right):
			if left[i] <= right[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = right[j]
				j += 1
				count += len(left) - i
			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


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

def merge_sort(arr):
	if len(arr) <= 1:
		return (arr, 0)
	mid = len(arr) // 2
	(left, l_c) = merge_sort(arr[:mid])
	(right, r_c) = merge_sort(arr[mid:])
	(merged, i_c) = merge(left, right)
	return (merged, l_c + r_c + i_c)

class Solution:

	def inversionCount(self, arr, n):
		(_, i) = merge_sort(arr)
		return i


class Solution:

	def merge_sort(self, arr, start, end):
		if start < end:
			mid = (start + end) // 2
			left_swaps = self.merge_sort(arr, start, mid)
			right_swaps = self.merge_sort(arr, mid + 1, end)
			total_swaps = left_swaps + right_swaps
			total_swaps += self.merge(arr, start, mid, end)
			return total_swaps
		else:
			return 0

	def merge(self, arr, start, mid, end):
		left_arr = arr[start:mid + 1]
		right_arr = arr[mid + 1:end + 1]
		i = 0
		j = 0
		k = start
		swaps = 0
		while i < len(left_arr) and j < len(right_arr):
			if left_arr[i] <= right_arr[j]:
				arr[k] = left_arr[i]
				i += 1
			else:
				arr[k] = right_arr[j]
				j += 1
				swaps += mid - start + 1 - i
			k += 1
		while i < len(left_arr):
			arr[k] = left_arr[i]
			i += 1
			k += 1
		while j < len(right_arr):
			arr[k] = right_arr[j]
			j += 1
			k += 1
		return swaps

	def inversionCount(self, arr, n):
		return self.merge_sort(arr, 0, n - 1)


class Solution:

	def merge(self, arr, l, m, h):
		i = l
		j = m + 1
		c = 0
		new_array = []
		while i <= m and j <= h:
			if arr[i] > arr[j]:
				new_array.append(arr[j])
				c += m - i + 1
				j += 1
			else:
				new_array.append(arr[i])
				i += 1
		while i <= m:
			new_array.append(arr[i])
			i += 1
		while j <= h:
			new_array.append(arr[j])
			j += 1
		i = 0
		while i < h - l + 1:
			arr[i + l] = new_array[i]
			i += 1
		return c

	def merge_sort_count_inversions(self, arr, l, h):
		if l < h:
			m = l + (h - l) // 2
			left_count = self.merge_sort_count_inversions(arr, l, m)
			right_count = self.merge_sort_count_inversions(arr, m + 1, h)
			left_right_merge_count = self.merge(arr, l, m, h)
			return left_count + right_count + left_right_merge_count
		return 0

	def inversionCount(self, arr, n):
		return self.merge_sort_count_inversions(arr, 0, n - 1)


class Solution:

	def merge(self, start, mid, end, arr):
		i = start
		j = mid + 1
		count = 0
		ans = []
		while i <= mid and j <= end:
			if arr[i] <= arr[j]:
				ans.append(arr[i])
				i += 1
			else:
				count += mid - i + 1
				ans.append(arr[j])
				j += 1
		while i <= mid:
			ans.append(arr[i])
			i += 1
		while j <= end:
			ans.append(arr[j])
			j += 1
		for i in range(end - start + 1):
			arr[start] = ans[i]
			start += 1
		return count

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

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


def merge(arr, l, m, r):
	n1 = m - l + 1
	n2 = r - m
	A = [arr[l + i] for i in range(n1)]
	B = [arr[m + 1 + j] for j in range(n2)]
	i = 0
	j = 0
	k = l
	count = 0
	while i < n1 and j < n2:
		if A[i] > B[j]:
			count += n1 - i
			arr[k] = B[j]
			k += 1
			j += 1
		else:
			arr[k] = A[i]
			k += 1
			i += 1
	while i < n1:
		arr[k] = A[i]
		k += 1
		i += 1
	while j < n2:
		arr[k] = B[j]
		k += 1
		j += 1
	return count

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

class Solution:

	def inversionCount(self, arr, n):
		left = 0
		right = n - 1
		return mergeSort(arr, left, right)


import sys

class Solution:

	def inversionCount(self, arr, n):

		def dnc(arr):
			if not arr:
				return
			if len(arr) <= 1:
				return (arr, 0)
			else:
				larr = arr[:len(arr) // 2]
				rarr = arr[len(arr) // 2:]
				(l, lic) = dnc(larr)
				(r, ric) = dnc(rarr)
				invcount = lic + ric
				(li, ri, ki) = (0, 0, 0)
				finarr = [0] * (len(l) + len(r))
				while li < len(l) and ri < len(r) and (ki < len(finarr)):
					if l[li] > r[ri]:
						finarr[ki] = r[ri]
						ri += 1
						ki += 1
						invcount += len(l) - li
					else:
						finarr[ki] = l[li]
						li += 1
						ki += 1
				while li < len(l):
					finarr[ki] = l[li]
					li += 1
					ki += 1
				while ri < len(r):
					finarr[ki] = r[ri]
					ri += 1
					ki += 1
				return (finarr, invcount)
		(_, n) = dnc(arr)
		return n


class Solution:

	def inversionCount(self, arr, n):
		copy = arr.copy()
		return self.mergeSort(copy, 0, n - 1)

	def mergeSort(self, arr, start, end):
		if start >= end:
			return 0
		mid = (start + end) // 2
		cnt = 0
		cnt += self.mergeSort(arr, start, mid)
		cnt += self.mergeSort(arr, mid + 1, end)
		cnt += self.merge(arr, start, mid, end)
		return cnt

	def merge(self, arr, start, mid, end):
		sizeOne = mid - start + 1
		sizeTwo = end - mid
		left = []
		for i in range(sizeOne):
			left.append(arr[i + start])
		right = []
		for i in range(sizeTwo):
			right.append(arr[i + mid + 1])
		i = j = cnt = 0
		k = start
		while i < sizeOne and j < sizeTwo:
			if left[i] > right[j]:
				cnt += sizeOne - i
				arr[k] = right[j]
				k += 1
				j += 1
			else:
				arr[k] = left[i]
				k += 1
				i += 1
		while i < sizeOne:
			arr[k] = left[i]
			k += 1
			i += 1
		while j < sizeTwo:
			arr[k] = right[j]
			k += 1
			j += 1
		return cnt


class Solution:

	def __init__(self):
		self.count = 0

	def inversionCount(self, arr, n):
		low = 0
		high = n - 1

		def mergesort(low, high):
			mid = (high + low) // 2
			if low < high:
				count = mergesort(low, mid) + mergesort(mid + 1, high)
				i = low
				j = mid + 1
				while i < mid + 1 and j < high + 1:
					if arr[i] > arr[j]:
						count += mid - i + 1
						j += 1
					else:
						i += 1
				arr[low:high + 1] = sorted(arr[low:high + 1])
				return count
			else:
				return 0
		return mergesort(0, n - 1)


class Solution:

	def inversionCount(self, arr, n):
		inversions = {'ct': 0}

		def merge(A, B):
			new = []
			i = j = 0
			(n, m) = (len(A), len(B))
			while i + j < n + m:
				if i > n - 1:
					new = new + B[j:]
					break
				if j > m - 1:
					new = new + A[i:]
					break
				if A[i] <= B[j]:
					new.append(A[i])
					i += 1
				else:
					inversions['ct'] += n - i
					new.append(B[j])
					j += 1
			return new

		def mergeSort(arr):
			if len(arr) == 1:
				return arr
			n = len(arr)
			a = arr[:n // 2]
			b = arr[n // 2:]
			return merge(mergeSort(a), mergeSort(b))
		mergeSort(arr)
		return inversions['ct']


class Solution:

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

	def merge(self, arr, left, right):
		if right <= left:
			return
		mid = (left + right) // 2
		self.merge(arr, left, mid)
		self.merge(arr, mid + 1, right)
		arr[left:right + 1] = self.mergearrays(arr[left:mid + 1], arr[mid + 1:right + 1])

	def inversionCount(self, arr, n):
		self.count = 0
		self.merge(arr, 0, len(arr) - 1)
		return self.count


from typing import List

class Solution:

	def inversionCount(self, arr, n):

		def merge(arr, temp, left, mid, right) -> int:
			c = 0
			i = left
			j = mid
			k = left
			while i <= mid - 1 and j <= right:
				if arr[i] <= arr[j]:
					temp[k] = arr[i]
					k += 1
					i += 1
				else:
					temp[k] = arr[j]
					k += 1
					j += 1
					c += mid - i
			while i <= mid - 1:
				temp[k] = arr[i]
				k += 1
				i += 1
			while j <= right:
				temp[k] = arr[j]
				k += 1
				j += 1
			for l in range(left, right + 1):
				arr[l] = temp[l]
			return c

		def mergesort(arr: List[int], temp: List[int], i: int, j: int) -> int:
			c = 0
			if j > i:
				m = (i + j) // 2
				c += mergesort(arr, temp, i, m)
				c += mergesort(arr, temp, m + 1, j)
				c += merge(arr, temp, i, m + 1, j)
			return c
		temp = [0] * n
		return mergesort(arr, temp, 0, n - 1)


class Solution:

	def __inversionCount(self, arr, l, m, r):
		left = arr[l:m + 1]
		right = arr[m + 1:r + 1]
		i = j = 0
		k = l
		inversions = 0
		(n1, n2) = (len(left), len(right))
		while i < n1 and j < n2:
			if left[i] <= right[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = right[j]
				j += 1
				inversions += len(left) - 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 inversions

	def __inversion_count_sort(self, arr, l, r):
		inversions = 0
		if r > l:
			m = (l + r) // 2
			inversions += self.__inversion_count_sort(arr, l, m)
			inversions += self.__inversion_count_sort(arr, m + 1, r)
			inversions += self.__inversionCount(arr, l, m, r)
		return inversions

	def inversionCount(self, arr, n):
		return self.__inversion_count_sort(arr, 0, n)


class Solution:

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

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

	def merge(self, a, l, m, r):
		ls = list()
		i = l
		j = m + 1
		count = 0
		while i <= m and j <= r:
			if a[i] > a[j]:
				count += m - i + 1
				ls.append(a[j])
				j += 1
			else:
				ls.append(a[i])
				i += 1
		while i <= m:
			ls.append(a[i])
			i += 1
		while j <= r:
			ls.append(a[j])
			j += 1
		i = l
		k = 0
		while i <= r:
			a[i] = ls[k]
			i += 1
			k += 1
		return count


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

class Solution:

	def inversionCount(self, arr, n):
		return mergeSort(arr, n)


class Solution:
	count = 0

	def mergesort(self, arr, n):
		if n > 1:
			mid = n // 2
			l = arr[:mid]
			r = arr[mid:]
			self.mergesort(l, len(l))
			self.mergesort(r, len(r))
			i = j = k = 0
			while i < len(l) and j < len(r):
				if l[i] <= r[j]:
					arr[k] = l[i]
					i += 1
				else:
					arr[k] = r[j]
					j += 1
					self.count += len(l) - i
				k += 1
			while i < len(l):
				arr[k] = l[i]
				i += 1
				k += 1
			while j < len(r):
				arr[k] = r[j]
				j += 1
				k += 1

	def inversionCount(self, arr, n):
		self.mergesort(arr, n)
		return self.count


class Solution:

	def inversionCount(self, arr, n):
		sys.setrecursionlimit(1000000)
		return self.ms(arr, 0, n - 1)

	def ms(self, arr, i, j):
		if i < j:
			m = (i + j) // 2
			return self.ms(arr, i, m) + self.ms(arr, m + 1, j) + self.mrg(arr, i, m, j)
		return 0

	def mrg(self, arr, x, m, y):
		L = arr[x:m + 1]
		R = arr[m + 1:y + 1]
		(n1, n2) = (len(L), len(R))
		(i, j, k) = (0, 0, x)
		ans = 0
		while i < n1 and j < n2:
			if L[i] > R[j]:
				ans += n1 - i
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			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 ans


class Solution:

	def mergesort(self, arr):
		if len(arr) > 1:
			mid = len(arr) // 2
			L = arr[:mid]
			R = arr[mid:]
			self.mergesort(L)
			self.mergesort(R)
			i = j = k = 0
			while i < len(L) and j < len(R):
				if L[i] <= R[j]:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					self.inv_count += mid - i
					j += 1
				k += 1
			while i < len(L):
				arr[k] = L[i]
				i += 1
				k += 1
			while j < len(R):
				arr[k] = R[j]
				j += 1
				k += 1

	def inversionCount(self, arr, n):
		self.inv_count = 0
		self.mergesort(arr)
		return self.inv_count


class Solution:

	def merge(self, arr, low, mid, high):
		left = arr[low:mid + 1]
		right = arr[mid + 1:high + 1]
		(i, j, k, res) = (0, 0, low, 0)
		while i < len(left) and j < len(right):
			if left[i] <= right[j]:
				arr[k] = left[i]
				k += 1
				i += 1
			else:
				arr[k] = right[j]
				res += len(left) - i
				k += 1
				j += 1
		while i < len(left):
			arr[k] = left[i]
			k += 1
			i += 1
		while j < len(right):
			arr[k] = right[j]
			k += 1
			j += 1
		return res

	def inversionCountHelper(self, arr, low, high):
		res = 0
		if low < high:
			mid = (low + high) // 2
			res += self.inversionCountHelper(arr, low, mid)
			res += self.inversionCountHelper(arr, mid + 1, high)
			res += self.merge(arr, low, mid, high)
		return res

	def inversionCount(self, arr, n):
		return self.inversionCountHelper(arr, 0, n - 1)


class Solution:

	def inversionCount(self, a, n):
		ans = [0]

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

		def mergesort(i, j, ans):
			if i == j:
				return [a[i]]
			if i < j:
				mid = i + (j - i) // 2
				left = mergesort(i, mid, ans)
				right = mergesort(mid + 1, j, ans)
				mer = merge(left, right, ans)
				return mer
			return
		mergesort(0, n - 1, ans)
		return ans[0]


class Solution:

	def mergeSort(self, tmp, arr, s, e):
		if s >= e:
			return 0
		m = (s + e) // 2
		r = 0
		r += self.mergeSort(tmp, arr, s, m)
		r += self.mergeSort(tmp, arr, m + 1, e)
		i = s
		j = m + 1
		k = s
		while i < m + 1 and j <= e:
			if arr[i] <= arr[j]:
				tmp[k] = arr[i]
				i += 1
				k += 1
			else:
				tmp[k] = arr[j]
				j += 1
				k += 1
				r += m - i + 1
		while i < m + 1:
			tmp[k] = arr[i]
			i += 1
			k += 1
		while j <= e:
			tmp[k] = arr[j]
			j += 1
			k += 1
		for i in range(s, e + 1):
			arr[i] = tmp[i]
		return r

	def inversionCount(self, arr, n):
		tmp = [0] * n
		return self.mergeSort(tmp, arr, 0, n - 1)


class Solution:

	def inversionCount(self, arr, n):
		return self.countInversion(arr, 0, n - 1)

	def mergeCountInversion(self, arr, l, m, r):
		(i, j) = (0, 0)
		(arr1, arr2) = (arr[l:m + 1], arr[m + 1:r + 1])
		(count, k) = (0, l)
		while i < len(arr1) and j < len(arr2):
			if arr1[i] <= arr2[j]:
				arr[k] = arr1[i]
				i += 1
			else:
				arr[k] = arr2[j]
				count += len(arr1) - i
				j += 1
			k += 1
		while i < len(arr1):
			arr[k] = arr1[i]
			i += 1
			k += 1
		while j < len(arr2):
			arr[k] = arr2[j]
			j += 1
			k += 1
		return count

	def countInversion(self, arr, l, r):
		res = 0
		if r > l:
			m = l + (r - l) // 2
			res += self.countInversion(arr, l, m)
			res += self.countInversion(arr, m + 1, r)
			res += self.mergeCountInversion(arr, l, m, r)
		return res


class Solution:

	def inversionCount(self, arr, n):

		def merge(arr, i, j, n):
			beg = i
			size2 = j
			temp = [0] * (n - i)
			k = 0
			while i < size2 and j < n:
				if arr[j] < arr[i]:
					self.count += size2 - i
					temp[k] = arr[j]
					j += 1
				else:
					temp[k] = arr[i]
					i += 1
				k += 1
			while i < size2:
				temp[k] = arr[i]
				i += 1
				k += 1
			while j < n:
				temp[k] = arr[j]
				j += 1
				k += 1
			l = 0
			for k in range(beg, n):
				arr[k] = temp[l]
				l += 1

		def divide(arr, start, end, size):
			if size > 1:
				mid_len = size // 2
				divide(arr, start, start + mid_len, mid_len)
				divide(arr, start + mid_len, end, size - mid_len)
				merge(arr, start, start + mid_len, end)
		self.count = 0
		divide(arr, 0, n, n)
		return self.count


class Solution:

	def __init__(self):
		self.ans = 0

	def merge(self, arr, low, mid, high):
		l = [0 for x in range(high - low + 1)]
		i = low
		j = mid + 1
		k = 0
		while i <= mid and j <= high:
			if arr[i] > arr[j]:
				self.ans = self.ans + mid - i + 1
				l[k] = arr[j]
				k = k + 1
				j = j + 1
			else:
				l[k] = arr[i]
				k = k + 1
				i = i + 1
		while i <= mid:
			l[k] = arr[i]
			i = i + 1
			k = k + 1
		while j <= high:
			l[k] = arr[j]
			j = j + 1
			k = k + 1
		k = 0
		for i in range(low, high + 1):
			arr[i] = l[k]
			k = k + 1

	def mergesort(self, arr, low, high):
		if low < high:
			mid = (low + high) // 2
			self.mergesort(arr, low, mid)
			self.mergesort(arr, mid + 1, high)
			self.merge(arr, low, mid, high)

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


class Solution:

	def inversionCount(self, arr, n):

		def ms(nums):
			inv = 0
			if len(nums) > 1:
				mid = len(nums) // 2
				left = nums[:mid]
				right = nums[mid:]
				inv += ms(left)
				inv += ms(right)
				inv += m(left, right, nums)
			return inv

		def m(left, right, nums):
			len_a = len(left)
			len_b = len(right)
			i = j = k = inv = 0
			while i < len_a and j < len_b:
				if left[i] > right[j]:
					nums[k] = right[j]
					j += 1
					inv = inv + len_a - i
				else:
					nums[k] = left[i]
					i += 1
				k += 1
			while j < len_b:
				nums[k] = right[j]
				j += 1
				k += 1
			while i < len_a:
				nums[k] = left[i]
				i += 1
				k += 1
			return inv
		return ms(arr)


class Solution:

	def merge(self, nums, l, m, r):
		nums1 = nums[l:m + 1]
		nums2 = nums[m + 1:r + 1]
		count = 0
		l1 = m - l + 1
		l2 = r - m
		i = 0
		j = 0
		k = l
		while i < l1 and j < l2:
			if nums1[i] <= nums2[j]:
				nums[k] = nums1[i]
				i += 1
				k += 1
			else:
				nums[k] = nums2[j]
				j += 1
				k += 1
				count += l1 - i
		while i < l1:
			nums[k] = nums1[i]
			i += 1
			k += 1
		while j < l2:
			nums[k] = nums2[j]
			j += 1
			k += 1
		return count

	def inverse(self, nums, l, r):
		count = 0
		if l >= r:
			return count
		m = int((l + r) / 2)
		count += self.inverse(nums, l, m)
		count += self.inverse(nums, m + 1, r)
		count += self.merge(nums, l, m, r)
		return count

	def inversionCount(self, nums, n):
		return self.inverse(nums, 0, n - 1)


class Solution:

	def inversionCount(self, arr, n):

		def merge_and_count(a, b):
			c = []
			(i, j, inversions) = (0, 0, 0)
			while i < len(a) and j < len(b):
				if a[i] > b[j]:
					c.append(b[j])
					inversions += len(a) - i
					j += 1
				else:
					c.append(a[i])
					i += 1
			while i < len(a):
				c.append(a[i])
				i += 1
			while j < len(b):
				c.append(b[j])
				j += 1
			return (inversions, c)

		def sort_and_count(arr, l, r):
			if l == r:
				return (0, [arr[l]])
			m = (l + r) // 2
			(ra, a) = sort_and_count(arr, l, m)
			(rb, b) = sort_and_count(arr, m + 1, r)
			(rab, ab) = merge_and_count(a, b)
			return (ra + rb + rab, ab)
		(count, l) = sort_and_count(arr, 0, len(arr) - 1)
		return count


class Solution:

	def inversionCount(self, arr, n):

		def merge(arr, low, mid, high):
			i = 0
			j = 0
			k = low
			left = arr[low:mid + 1]
			right = arr[mid + 1:high + 1]
			l = len(left)
			r = len(right)
			count = 0
			while i < l and j < r:
				if left[i] <= right[j]:
					arr[k] = left[i]
					i += 1
					k += 1
				else:
					count += l - i
					arr[k] = right[j]
					j += 1
					k += 1
			while i < l:
				arr[k] = left[i]
				i += 1
				k += 1
			while j < r:
				arr[k] = right[j]
				j += 1
				k += 1
			return count

		def merge_sort(arr, low, high):
			sum = 0
			if low < high:
				mid = (low + high) // 2
				sum += merge_sort(arr, low, mid)
				sum += merge_sort(arr, mid + 1, high)
				sum += merge(arr, low, mid, high)
			return sum
		return merge_sort(arr, 0, n - 1)


class Solution:

	def inversionCount(self, arr, n):

		def mergeSortAndCount(arr, l, r):
			count = 0
			if l < r:
				m = (l + r) // 2
				count += mergeSortAndCount(arr, l, m)
				count += mergeSortAndCount(arr, m + 1, r)
				i = j = 0
				left = arr[l:m + 1]
				right = arr[m + 1:r + 1]
				for k in range(l, r + 1):
					if i >= len(left):
						arr[k] = right[j]
						j += 1
					elif j >= len(right):
						arr[k] = left[i]
						i += 1
					elif left[i] <= right[j]:
						arr[k] = left[i]
						i += 1
					else:
						arr[k] = right[j]
						j += 1
						count += m + 1 - (l + i)
			return count
		return mergeSortAndCount(arr, 0, n - 1)


class Solution:

	def inversionCount(self, arr, n):
		if n == 1:
			return 0
		mid = n // 2
		left_arr = arr[:mid]
		right_arr = arr[mid:]
		count = self.inversionCount(left_arr, mid) + self.inversionCount(right_arr, n - mid)
		i = j = k = 0
		while i < mid and j < n - mid:
			if left_arr[i] <= right_arr[j]:
				arr[k] = left_arr[i]
				i += 1
			else:
				arr[k] = right_arr[j]
				count += mid - i
				j += 1
			k += 1
		while i < mid:
			arr[k] = left_arr[i]
			i += 1
			k += 1
		while j < n - mid:
			arr[k] = right_arr[j]
			j += 1
			k += 1
		return count


class Solution:

	def inversionCount(self, A, n):
		ans = [0] * n
		s = 0
		e = n - 1

		def merge_sort(A, ans, s, e):
			ic = 0
			if s == e:
				return 0
			mid = (s + e) // 2
			ic += merge_sort(A, ans, s, mid)
			ic += merge_sort(A, ans, mid + 1, e)
			ic += merge(A, ans, s, mid, e)
			return ic

		def merge(A, ans, s, mid, e):
			count = 0
			(i, j, k) = (s, mid + 1, s)
			while i <= mid and j <= e:
				if A[i] <= A[j]:
					ans[k] = A[i]
					i += 1
					k += 1
				else:
					count += mid + 1 - i
					ans[k] = A[j]
					j += 1
					k += 1
			while i <= mid:
				ans[k] = A[i]
				i += 1
				k += 1
			while j <= e:
				ans[k] = A[j]
				j += 1
				k += 1
			for i in range(s, e + 1):
				A[i] = ans[i]
			return count
		return merge_sort(A, ans, s, e)


class Solution:

	def inversionCount(self, arr, n):

		def helper(left, right):
			if left >= right:
				return 0
			mid = (left + right) // 2
			cnt = helper(left, mid) + helper(mid + 1, right)
			sa1 = arr[left:mid + 1]
			sa2 = arr[mid + 1:right + 1]
			(i, j) = (0, 0)
			while i < len(sa1) and j < len(sa2):
				if sa1[i] <= sa2[j]:
					arr[left] = sa1[i]
					i += 1
				else:
					cnt += len(sa1) - i
					arr[left] = sa2[j]
					j += 1
				left += 1
			while i < len(sa1):
				arr[left] = sa1[i]
				i += 1
				left += 1
			while j < len(sa2):
				arr[left] = sa2[j]
				j += 1
				left += 1
			return cnt
		cn = helper(0, len(arr))
		return cn