An element Y is said to be the surpasser of element X if it is a greater element on the right of X. ie, if X = arr[i] and Y = arr[j], i<j and Arr[i] < Arr[j]. 
Given an array of size N containing distinct integers, find the number of surpassers for each of its elements.
Example 1:
Input:
N = 5
Arr[] = {4, 5, 1, 2, 3}
Output: 1 0 2 1 0
Explanation: There are no elements greater 
than 3 at the right of 3. There is one 
element at right of 2 and greater than 2. 
There are 2 elements greater than 1 at the 
right of 1. And so on.
Example 2:
Input:
N = 6
Arr[] = {2, 7, 5, 3, 8, 1}
Output: 4 1 1 1 0 0
Your Task:
You don't need to read input or print anything. Your task is to complete the function findSurpasser() which takes the array of integers arr and n as input parameters and returns an array of integers of size N denoting the surpasser count of each element of arr.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def findSurpasser(self, arr, n):

        # code here

Solutions:
class Solution:

	def findSurpasser(self, arr, n):
		d = {}

		def merge(l, m, r):
			L = arr[l:m + 1]
			R = arr[m + 1:r + 1]
			i = 0
			j = 0
			k = l
			c = 0
			while i < len(L) and j < len(R):
				if L[i] < R[j]:
					arr[k] = L[i]
					d[L[i]] = d.get(L[i], 0) + c
					i += 1
					k += 1
				else:
					arr[k] = R[j]
					c += 1
					j += 1
					k += 1
			while j < len(R):
				arr[k] = R[j]
				c += 1
				j += 1
				k += 1
			while i < len(L):
				arr[k] = L[i]
				d[L[i]] = d.get(L[i], 0) + c
				i += 1
				k += 1

		def mergesort(i, j):
			if j - i > 0:
				m = i + (j - i) // 2
				mergesort(i, m)
				mergesort(m + 1, j)
				merge(i, m, j)
		ans = []
		du = arr[:]
		mergesort(0, n - 1)
		for i in du:
			ans.append(n - 1 - d.get(i, 0))
			n -= 1
		return ans


import bisect

class Solution:

	def construct(self, v, tl, tr):
		if tl == tr:
			self.t[v] = self.data[tl]
		else:
			tm = (tl + tr) // 2
			self.construct(2 * v + 1, tl, tm)
			self.construct(2 * v + 2, tm + 1, tr)
			self.t[v] = self.t[2 * v + 1] + self.t[2 * v + 2]

	def query(self, v, tl, tr, l, r):
		if l > r:
			return 0
		if l == tl and r == tr:
			return self.t[v]
		tm = (tl + tr) // 2
		return self.query(2 * v + 1, tl, tm, l, min(r, tm)) + self.query(2 * v + 2, tm + 1, tr, max(l, tm + 1), r)

	def update(self, v, tl, tr, pos, val):
		if tl == tr:
			self.t[v] += val
		else:
			tm = (tl + tr) // 2
			if pos <= tm:
				self.update(2 * v + 1, tl, tm, pos, val)
			else:
				self.update(2 * v + 2, tm + 1, tr, pos, val)
			self.t[v] = self.t[2 * v + 1] + self.t[2 * v + 2]

	def findSurpasser(self, arr, n):
		temp = arr.copy()
		temp.sort()
		for i in range(n):
			idx = bisect.bisect(temp, arr[i])
			arr[i] = idx
		self.data = [0] * (n + 1)
		self.t = [0] * 4 * (n + 1)
		self.construct(0, 0, n)
		ans = [0] * n
		for i in range(n - 1, -1, -1):
			ans[i] = self.query(0, 0, n, arr[i] + 1, n)
			self.update(0, 0, n, arr[i], 1)
		return ans


import bisect

class Solution:

	def sum(self, bit, idx):
		ans = 0
		idx += 1
		while idx > 0:
			ans += bit[idx]
			idx -= idx & -idx
		return ans

	def update(self, bit, n, idx, val):
		idx += 1
		while idx < n:
			bit[idx] += val
			idx += idx & -idx

	def findSurpasser(self, arr, n):
		temp = arr.copy()
		temp.sort()
		for i in range(n):
			idx = bisect.bisect(temp, arr[i])
			arr[i] = idx
		bit = [0] * (n + 1)
		ans = [0] * n
		for i in range(n - 1, -1, -1):
			inv = self.sum(bit, arr[i] - 1)
			ans[i] = n - 1 - i - inv
			self.update(bit, n + 1, arr[i], 1)
		return ans


from sortedcontainers import SortedList
from bisect import bisect_left

class Solution:

	def findSurpasser(self, arr, n):
		s = SortedList()
		res = [0] * n
		for i in range(n - 1, -1, -1):
			ind = bisect_left(s, arr[i], 0, len(s))
			res[i] = len(s) - ind
			s.add(arr[i])
		return res


from bisect import bisect

class Solution:

	def findSurpasser(self, arr, n):
		output = []
		brr = []
		for item in arr[::-1]:
			i = bisect(brr, item)
			output.append(len(brr) - i)
			brr.insert(i, item)
		return output[::-1]


class Solution:

	def findSurpasser(self, arr, n):
		ans = [0] * n
		arrr = []
		for i in range(len(arr)):
			arrr.append((arr[i], i))

		def merge(low, mid, high):
			left = []
			right = []
			for i in range(low, mid + 1):
				left.append(arrr[i])
			for i in range(mid + 1, high + 1):
				right.append(arrr[i])
			i = 0
			j = 0
			while i < len(left) and j < len(right):
				if left[i][0] < right[j][0]:
					p = left[i][1]
					ans[p] += len(right) - j
					arrr[low] = left[i]
					i += 1
				else:
					arrr[low] = right[j]
					j += 1
				low += 1
			while i < len(left):
				arrr[low] = left[i]
				i += 1
				low += 1
			while j < len(right):
				arrr[low] = right[j]
				j += 1
				low += 1

		def mergesort(low, high):
			if low == high:
				return
			mid = (low + high) // 2
			left = mergesort(low, mid)
			right = mergesort(mid + 1, high)
			merge(low, mid, high)
		mergesort(0, n - 1)
		return ans


class Solution:

	def findSurpasser(self, arr, n):
		cnt = {}
		dup = arr[:]
		self.merge_sort(dup, 0, n - 1, cnt)
		surpass = [0] * n
		for i in range(n):
			if arr[i] in cnt:
				surpass[i] = n - 1 - i - cnt[arr[i]]
		return surpass

	def merge_sort(self, arr, l, r, cnt):
		if l < r:
			mid = l + (r - l) // 2
			self.merge_sort(arr, l, mid, cnt)
			self.merge_sort(arr, mid + 1, r, cnt)
			self.merge(arr, l, mid, r, cnt)

	def merge(self, arr, l, m, r, cnt):
		n1 = m - l + 1
		n2 = r - m
		L = [0] * n1
		R = [0] * n2
		for i in range(n1):
			L[i] = arr[l + i]
		for i in range(n2):
			R[i] = arr[m + 1 + i]
		(i, j, k, c) = (0, 0, l, 0)
		while i < n1 and j < n2:
			if L[i] <= R[j]:
				if L[i] in cnt:
					cnt[L[i]] += c
				else:
					cnt[L[i]] = c
				arr[k] = L[i]
				i += 1
				k += 1
			else:
				arr[k] = R[j]
				j += 1
				k += 1
				c += 1
		while i < n1:
			if L[i] in cnt:
				cnt[L[i]] += c
			else:
				cnt[L[i]] = c
			arr[k] = L[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = R[j]
			j += 1
			k += 1


import bisect

class Solution:

	def findSurpasser(self, a, n):
		ans = []
		temp = []
		for i in range(n - 1, -1, -1):
			p = bisect.bisect_left(temp, a[i])
			ans.append(len(temp) - p)
			bisect.insort_left(temp, a[i])
		return ans[::-1]


from collections import defaultdict

class Solution:

	def findSurpasser(self, arr, n):
		hm = defaultdict(int)

		def merge(arr1, arr2):
			res = []
			(i, j) = (0, 0)
			while i < len(arr1) and j < len(arr2):
				if arr1[i] <= arr2[j]:
					hm[arr1[i]] += j
					res.append(arr1[i])
					i += 1
				else:
					res.append(arr2[j])
					j += 1
			while i < len(arr1):
				hm[arr1[i]] += j
				res.append(arr1[i])
				i += 1
			res.extend(arr2[j:])
			return res

		def mergesort(arr):
			if not arr:
				return []
			if len(arr) == 1:
				return arr
			mid = len(arr) // 2
			left = mergesort(arr[:mid])
			right = mergesort(arr[mid:])
			return merge(left, right)
		mergesort(arr)
		count = [0 for i in range(n)]
		for i in range(n):
			count[i] = n - i - hm[arr[i]] - 1
		return count


class Solution:

	def findSurpasser(self, arr, n):
		a = [arr[-1]]
		ans = [0]
		for i in range(-2, -n - 1, -1):
			l = 0
			u = len(a) - 1
			while l <= u:
				mid = (l + u) // 2
				if a[mid] > arr[i]:
					u = mid - 1
				else:
					l = mid + 1
			a.insert(l, arr[i])
			ans.append(len(a) - l - 1)
		return ans[::-1]


import bisect

class Solution:

	def findSurpasser(self, arr, n):
		sorted_ls = sorted(arr)
		ans = []
		for i in arr:
			j = bisect.bisect_left(sorted_ls, i)
			ans.append(len(sorted_ls) - j - 1)
			del sorted_ls[j]
		return ans


class Solution:

	def merge(self, p, q, r, arr, dp):
		tem = []
		i = p
		j = q + 1
		c = r - q
		while i <= q and j <= r:
			if arr[i] < arr[j]:
				dp[arr[i]] += c
				tem.append(arr[i])
				i += 1
			else:
				c -= 1
				tem.append(arr[j])
				j += 1
		while i <= q:
			tem.append(arr[i])
			i += 1
		while j <= r:
			tem.append(arr[j])
			j += 1
		n = len(tem)
		for i in range(n):
			arr[p + i] = tem[i]

	def mergesort(self, start, end, arr, dp):
		if start < end:
			mid = (start + end) // 2
			self.mergesort(start, mid, arr, dp)
			self.mergesort(mid + 1, end, arr, dp)
			self.merge(start, mid, end, arr, dp)

	def findSurpasser(self, arr, n):
		brr = arr.copy()
		dp = dict()
		for i in arr:
			dp[i] = 0
		self.mergesort(0, n - 1, brr, dp)
		ans = [0] * n
		for i in range(n):
			ans[i] = dp[arr[i]]
		return ans


from collections import defaultdict

class Solution:

	def findSurpasser(self, arr, n):

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

		def merge_sort(arr, temp, left, right):
			if left < right:
				mid = (left + right) // 2
				merge_sort(arr, temp, left, mid)
				merge_sort(arr, temp, mid + 1, right)
				merge(arr, temp, left, mid + 1, right)
		has = defaultdict(int)
		temp = [-1] * n
		copy = arr.copy()
		merge_sort(copy, temp, 0, n - 1)
		ans = []
		for i in range(n):
			res = n - 1 - i - has[arr[i]]
			ans.append(res)
		return ans


from bisect import bisect_right

class Solution:

	def findSurpasser(self, a, n):
		b = [0] * n
		l = [a[n - 1]]
		for i in range(n - 2, -1, -1):
			j = bisect_right(l, a[i])
			b[i] = len(l) - j
			l.insert(j, a[i])
		return b


import bisect

class Solution:

	def merge(self, arr, l, m, r, hm):
		n1 = m - l + 1
		n2 = r - m
		L = [0 for i in range(n1)]
		R = [0 for i in range(n2)]
		for i in range(n1):
			L[i] = arr[l + i]
		for j in range(n2):
			R[j] = arr[m + 1 + j]
		(i, j, k, c) = (0, 0, l, 0)
		while i < n1 and j < n2:
			if L[i] <= R[j]:
				if L[i] in hm:
					hm[L[i]] += c
				else:
					hm[L[i]] = c
				arr[k] = L[i]
				k += 1
				i += 1
			else:
				arr[k] = R[j]
				c += 1
				k += 1
				j += 1
		while i < n1:
			if L[i] in hm:
				hm[L[i]] += c
			else:
				hm[L[i]] = c
			arr[k] = L[i]
			k += 1
			i += 1
		while j < n2:
			arr[k] = R[j]
			k += 1
			j += 1

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

	def findSurpasser(self, arr, n):
		hm = {}
		dup = arr[:]
		sur = []
		self.mergeSort(dup, 0, n - 1, hm)
		for i in range(n):
			sur.append(n - 1 - i - (hm[arr[i]] if arr[i] in hm else 0))
		return sur


import bisect

class Solution:

	def findSurpasser(self, arr, n):
		ans = []
		res = []
		for i in range(n - 1, -1, -1):
			a = bisect.bisect_left(res, arr[i])
			ans.append(len(res) - a)
			bisect.insort_left(res, arr[i])
		return ans[::-1]


import bisect

class Solution:

	def findSurpasser(self, a, n):
		ans = []
		temp = []
		for i in range(n - 1, -1, -1):
			p = bisect.bisect_left(temp, a[i])
			ans.append(len(temp) - p)
			bisect.insort_left(temp, a[i])
		return ans[::-1]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findSurpasser(arr, n)
		for xx in ans:
			print(xx, end=' ')
		print()
		tc -= 1


class Solution:

	def findSurpasser(self, arr, n):

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

		def mergeSort(arr, l, r, hm):
			if l < r:
				m = l + (r - l) // 2
				mergeSort(arr, l, m, hm)
				mergeSort(arr, m + 1, r, hm)
				merge(arr, l, m, r, hm)
		hm = {}
		dup = arr[:]
		mergeSort(dup, 0, len(dup) - 1, hm)
		res = []
		n = len(arr)
		for i in range(len(arr)):
			if arr[i] in hm:
				res.append(n - 1 - i - hm[arr[i]])
			else:
				res.append(n - 1 - i)
		return res
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findSurpasser(arr, n)
		for xx in ans:
			print(xx, end=' ')
		print()
		tc -= 1


class Solution:

	def findSurpasser(self, arr, n):
		res = [0 for _ in range(n)]
		for i in range(n):
			arr[i] = [arr[i], i]

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

		def mergeSort(l, r):
			if l == r:
				return [arr[l]]
			m = l + r >> 1
			if l == m:
				return merge([arr[l]], [arr[r]])
			a = mergeSort(l, m - 1)
			b = mergeSort(m, r)
			return merge(a, b)
		mergeSort(0, n - 1)
		return res
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findSurpasser(arr, n)
		for xx in ans:
			print(xx, end=' ')
		print()
		tc -= 1


from heapq import heappush, heappop, heapify
from bisect import bisect, insort

class Solution:

	def findSurpasser(self, arr, n):
		surpass_arr = [0] * n
		heap = []
		for (i, v) in enumerate(arr):
			heappush(heap, (v, i))
		ind_list = []
		while heap:
			(val, org_ind) = heappop(heap)
			y = bisect(ind_list, org_ind)
			min_to_right = len(ind_list) - y
			max_to_right = n - 1 - org_ind - min_to_right
			surpass_arr[org_ind] = max_to_right
			insort(ind_list, org_ind)
		return surpass_arr
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findSurpasser(arr, n)
		for xx in ans:
			print(xx, end=' ')
		print()
		tc -= 1


class Solution:

	def findSurpasser(self, arr, n):
		Dict = {}

		def merge(arr, l, mid, r):
			n = mid - l + 1
			m = r - mid
			l1 = [0 for i in range(n)]
			r1 = [0 for i in range(m)]
			for i in range(n):
				l1[i] = arr[l + i]
			for j in range(m):
				r1[j] = arr[j + mid + 1]
			(i, j, k, count) = (0, 0, l, 0)
			while i < n and j < m:
				if l1[i] <= r1[j]:
					arr[k] = l1[i]
					if l1[i] in Dict:
						Dict[l1[i]] += m - j
					else:
						Dict[l1[i]] = m - j
					i += 1
					k += 1
				else:
					arr[k] = r1[j]
					j += 1
					k += 1
					count += n - i
			while i < n:
				arr[k] = l1[i]
				i += 1
				k += 1
			while j < m:
				arr[k] = r1[j]
				j += 1
				k += 1
			return count

		def mergeSort(arr, l, r):
			intervals = 0
			if l < r:
				mid = (l + r) // 2
				intervals += mergeSort(arr, l, mid)
				intervals += mergeSort(arr, mid + 1, r)
				intervals += merge(arr, l, mid, r)
			return intervals
		dup = arr[:]
		mergeSort(arr, 0, n - 1)
		ans = []
		for i in dup:
			if i in Dict:
				ans.append(Dict[i])
			else:
				ans.append(0)
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findSurpasser(arr, n)
		for xx in ans:
			print(xx, end=' ')
		print()
		tc -= 1


from bisect import bisect_left as BL

class Solution:

	def findSurpasser(self, a, n):
		z = []
		res = [0] * n
		for (i, e) in reversed(list(enumerate(a))):
			z.insert(BL(z, e), e)
			res[i] = n - i - 1 - BL(z, e)
		return res


class Solution:

	def findSurpasser(self, arr, n):

		def mergesort(arr, co, i, j):
			if i < j:
				mid = (i + j) // 2
				mergesort(arr, co, i, mid)
				mergesort(arr, co, mid + 1, j)
				c = 0
				t1 = i
				t2 = mid + 1
				l = []
				while t1 <= mid and t2 <= j:
					if arr[t1][1] <= arr[t2][1]:
						l.append(arr[t1])
						co[arr[t1][0]] += j - t2 + 1
						t1 += 1
					else:
						l.append(arr[t2])
						t2 += 1
				while t1 <= mid:
					l.append(arr[t1])
					co[arr[t1][0]] += 0
					t1 += 1
				while t2 <= j:
					l.append(arr[t2])
					t2 += 1
				for k in range(i, j + 1):
					arr[k] = l[k - i]
		an = [(i, arr[i]) for i in range(n)]
		co = [0 for i in range(n)]
		mergesort(an, co, 0, n - 1)
		return co


class Solution:

	def findSurpasser(self, arr, n):
		dup = arr.copy()
		_dict = {}
		start = 0
		end = n - 1
		self.mergeSort(dup, start, end, _dict)
		res = []
		for i in range(n):
			val = n - 1 - i
			if arr[i] in _dict:
				val = val - _dict[arr[i]]
			res.append(val)
		return res

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

	def merge(self, arr, start, mid, end, _dict):
		n1 = mid - start + 1
		n2 = end - mid
		L = [0 for _ in range(n1)]
		R = [0 for _ in range(n2)]
		for i in range(n1):
			L[i] = arr[start + i]
		for j in range(n2):
			R[j] = arr[mid + 1 + j]
		i = 0
		j = 0
		k = start
		c = 0
		while i < n1 and j < n2:
			if L[i] <= R[j]:
				if L[i] not in _dict:
					_dict[L[i]] = c
				else:
					_dict[L[i]] += c
				arr[k] = L[i]
				k += 1
				i += 1
			else:
				arr[k] = R[j]
				k += 1
				j += 1
				c += 1
		while i < n1:
			arr[k] = L[i]
			if L[i] not in _dict:
				_dict[L[i]] = c
			else:
				_dict[L[i]] += c
			k += 1
			i += 1
		while j < n2:
			arr[k] = R[j]
			k += 1
			j += 1
		return


class Solution:

	def __init__(self):
		self.um = {}

	def findSurpasser(self, arr, n):
		temp = arr.copy()
		ans = []
		self.mergeSort(temp, 0, n - 1)
		for i in range(n):
			ans.append(n - 1 - i - (self.um[arr[i]] if arr[i] in self.um else 0))
		return ans

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

	def merge(self, arr, left, right, mid):
		l = arr[left:mid + 1]
		r = arr[mid + 1:right + 1]
		i = 0
		j = 0
		k = left
		c = 0
		while i < len(l) and j < len(r):
			if l[i] <= r[j]:
				if l[i] not in self.um:
					self.um[l[i]] = c
				else:
					self.um[l[i]] += c
				arr[k] = l[i]
				i += 1
			else:
				arr[k] = r[j]
				c += 1
				j += 1
			k += 1
		while i < len(l):
			if l[i] not in self.um:
				self.um[l[i]] = c
			else:
				self.um[l[i]] += c
			arr[k] = l[i]
			i += 1
			k += 1
		while j < len(r):
			arr[k] = r[j]
			j += 1
			k += 1


class Solution:

	def findSurpasser(self, arr, n):
		mp = {a: 0 for a in arr}
		res = []
		self.merge_sort(arr[:], 0, n - 1, mp)
		for i in range(n):
			res.append(n - 1 - i - mp[arr[i]])
		return res

	def merge_sort(self, arr, l, r, mp):
		if l < r:
			m = (l + r) // 2
			self.merge_sort(arr, l, m, mp)
			self.merge_sort(arr, m + 1, r, mp)
			self.merge(arr, l, m, r, mp)

	def merge(self, arr, l, m, r, mp):
		(i, j, k) = (l, m + 1, l)
		tmp = []
		c = 0
		while i <= m and j <= r:
			if arr[i] < arr[j]:
				mp[arr[i]] += c
				tmp.append(arr[i])
				i += 1
			else:
				tmp.append(arr[j])
				c += 1
				j += 1
		while i <= m:
			mp[arr[i]] += c
			tmp.append(arr[i])
			i += 1
		while j <= r:
			tmp.append(arr[j])
			j += 1
		arr[l:r + 1] = tmp


from collections import OrderedDict

class Solution:

	def findSurpasser(self, arr, n):
		ma = OrderedDict()
		for e in arr:
			ma[e] = 0

		def merge(arr, m, l, r):
			n1 = m - l + 1
			n2 = r - m
			arr1 = []
			for i in range(n1):
				arr1.append(arr[i + l])
			arr2 = []
			for i in range(n2):
				arr2.append(arr[i + m + 1])
			i = 0
			j = 0
			c = n2
			k = l
			while i < n1 and j < n2:
				if arr1[i] <= arr2[j]:
					arr[k] = arr1[i]
					ma[arr1[i]] += c
					i += 1
					k += 1
				else:
					c -= 1
					arr[k] = arr2[j]
					j += 1
					k += 1
			while i < n1:
				arr[k] = arr1[i]
				ma[arr1[i]] += c
				i += 1
				k += 1
			while j < n2:
				arr[k] = arr2[j]
				j += 1
				k += 1

		def merge_sort(arr, l, r):
			if l < r:
				m = l + (r - l) // 2
				merge_sort(arr, l, m)
				merge_sort(arr, m + 1, r)
				merge(arr, m, l, r)
		merge_sort(arr, 0, n - 1)
		u = []
		for e in ma:
			u.append(ma[e])
		return u


class Solution:

	def count_smaller(self, nums):
		smaller_arr = [0] * len(nums)

		def merge_sort(nums):
			if len(nums) <= 1:
				return nums
			mid = len(nums) // 2
			left = merge_sort(nums[:mid])
			right = merge_sort(nums[mid:])
			return merge(left, right)

		def merge(left, right):
			result = []
			(l, r) = (0, 0)
			while l < len(left) or r < len(right):
				if r >= len(right) or (l < len(left) and left[l][1] <= right[r][1]):
					result.append(left[l])
					smaller_arr[left[l][0]] += r
					l += 1
				else:
					result.append(right[r])
					r += 1
			return result
		merge_sort(list(enumerate(nums)))
		return smaller_arr

	def findSurpasser(self, arr, n):
		lower_arr = self.count_smaller(arr)
		upper_arr = [n - i - 1 - lower_arr[i] for i in range(n)]
		return upper_arr


class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
		self.freq = 1
		self.size_right = 0

class Tree:

	def __init__(self, data):
		self.root = Node(data)

	def insert(self, arr, ans):
		for i in range(len(arr) - 2, -1, -1):
			data = arr[i]
			count = 0
			node = self.root
			while True:
				if data < node.data:
					count += node.size_right + node.freq
					if node.left:
						node = node.left
						continue
					else:
						node.left = Node(data)
						ans.append(count)
						break
				elif data == node.data:
					node.freq += 1
					ans.append(count + node.size_right)
					break
				else:
					node.size_right += 1
					if node.right:
						node = node.right
						continue
					else:
						node.right = Node(data)
						ans.append(count)
						break
from collections import defaultdict as dd

class Solution:

	def countInversions(self, arr):
		if len(arr) <= 1:
			return arr
		else:
			mid = len(arr) // 2
			l = self.countInversions(arr[:mid])
			r = self.countInversions(arr[mid:])
			i = 0
			j = 0
			c = 0
			res = []
			while i < len(l) and j < len(r):
				if l[i] <= r[j]:
					self.inversions[l[i]] += c
					arr[i + j] = l[i]
					i += 1
				else:
					c += 1
					arr[i + j] = r[j]
					j += 1
			while i < len(l):
				self.inversions[l[i]] += c
				arr[i + j] = l[i]
				i += 1
			while j < len(r):
				arr[i + j] = r[j]
				j += 1
			return arr

	def findSurpasser(self, arr, n):
		self.inversions = dd(int)
		dup = arr.copy()
		self.countInversions(arr)
		return [n - 1 - i - self.inversions[el] for (i, el) in enumerate(dup)]


class Solution:

	def findSurpasser(self, arr, n):
		surpasser = [0] * n
		index_value = [(i, v) for (i, v) in enumerate(arr)]
		self.merge_sort(index_value, surpasser)
		return surpasser

	def merge_sort(self, index_value, surpasser):
		if len(index_value) == 1:
			return index_value
		mid = len(index_value) // 2
		left = self.merge_sort(index_value[:mid], surpasser)
		right = self.merge_sort(index_value[mid:], surpasser)
		return self.merge(left, right, index_value, surpasser)

	def merge(self, left, right, index_value, surpasser):
		i = 0
		j = 0
		k = 0
		while i < len(left) or j < len(right):
			if j == len(right) or (i < len(left) and left[i][1] >= right[j][1]):
				index_value[k] = left[i]
				surpasser[left[i][0]] += j
				i += 1
			else:
				index_value[k] = right[j]
				j += 1
			k += 1
		return index_value


class Solution:

	def merge(self, arr, l, m, r, hm):
		(i, j, k) = (l, m, 0)
		a = [0] * (r - l)
		while i < m and j < r:
			if arr[i] < arr[j]:
				hm[arr[i]] += r - j
				a[k] = arr[i]
				i += 1
			else:
				a[k] = arr[j]
				j += 1
			k += 1
		while i < m:
			a[k] = arr[i]
			i += 1
			k += 1
		while j < r:
			a[k] = arr[j]
			j += 1
			k += 1
		k = 0
		for i in range(l, r):
			arr[i] = a[k]
			k += 1

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

	def findSurpasser(self, arr, n):
		hm = {}
		dup = arr[:]
		for x in arr:
			hm[x] = 0
		self.mergeSort(arr, 0, n, hm)
		for i in range(n):
			dup[i] = hm[dup[i]]
		return dup


class Solution:

	def merge(self, arr, hash_index, low, mid, high, result):
		(pointer1, pointer2) = (low, mid + 1)
		temp_arr = []
		while pointer1 <= mid and pointer2 <= high:
			if arr[pointer1] < arr[pointer2]:
				key = arr[pointer1]
				result[hash_index[key]] += high - pointer2 + 1
				temp_arr.append(key)
				pointer1 += 1
			else:
				key = arr[pointer2]
				temp_arr.append(key)
				pointer2 += 1
		while pointer1 <= mid:
			key = arr[pointer1]
			temp_arr.append(key)
			pointer1 += 1
		while pointer2 <= high:
			key = arr[pointer2]
			temp_arr.append(key)
			pointer2 += 1
		for index in range(low, high + 1):
			arr[index] = temp_arr[index - low]

	def merge_sort(self, arr, hash_index, low, high, result):
		if low >= high:
			return
		mid = (low + high) // 2
		self.merge_sort(arr, hash_index, low, mid, result)
		self.merge_sort(arr, hash_index, mid + 1, high, result)
		self.merge(arr, hash_index, low, mid, high, result)

	def findSurpasser(self, arr, n):
		result = [0 for i in range(n)]
		hash_index = {}
		for (index, num) in enumerate(arr):
			hash_index[num] = index
		self.merge_sort(arr, hash_index, 0, n - 1, result)
		return result


class Solution:

	def findSurpasser(self, arr, n):

		def merge(arr, tmp, l, m, r, mp):
			(i, j, k) = (l, m, l)
			cnt = 0
			while i <= m - 1 and j <= r:
				if arr[i] <= arr[j]:
					tmp[k] = arr[i]
					mp[arr[i]] += cnt
					i += 1
					k += 1
				else:
					tmp[k] = arr[j]
					j += 1
					k += 1
					cnt += 1
			while i <= m - 1:
				mp[arr[i]] += cnt
				tmp[k] = arr[i]
				i += 1
				k += 1
			while j <= r:
				tmp[k] = arr[j]
				j += 1
				k += 1
			for idx in range(l, r + 1, 1):
				arr[idx] = tmp[idx]

		def mergeSort(arr, tmp, l, r, mp):
			if r > l:
				m = l + (r - l) // 2
				mergeSort(arr, tmp, l, m, mp)
				mergeSort(arr, tmp, m + 1, r, mp)
				merge(arr, tmp, l, m + 1, r, mp)
		tmp = [0] * n
		mp = {}
		for nm in arr:
			mp[nm] = 0
		arr2 = []
		for nm in arr:
			arr2.append(nm)
		mergeSort(arr, tmp, 0, n - 1, mp)
		res = []
		for i in range(n):
			res.append(n - 1 - i - mp[arr2[i]])
		mp.clear()
		return res


class Solution:

	def findSurpasser(self, arr, n):
		e = [[i, x] for (i, x) in enumerate(arr)]
		bigger = [0] * n
		self.merge_sort(e, bigger)
		return bigger

	def merge_sort(self, e, bigger):
		if len(e) == 1:
			return e
		mid = len(e) // 2
		left = self.merge_sort(e[:mid], bigger)
		right = self.merge_sort(e[mid:], bigger)
		self.merge(left, right, e, bigger)
		return e

	def merge(self, left, right, e, bigger):
		(i, j, k) = (0, 0, 0)
		while i < len(left) or j < len(right):
			if j == len(right) or (i < len(left) and left[i][1] >= right[j][1]):
				e[k] = left[i]
				bigger[left[i][0]] += j
				i += 1
			else:
				e[k] = right[j]
				j += 1
			k += 1
		return


from bisect import bisect_right

class Solution:

	def findSurpasser(self, arr, n):
		d = []
		k = []
		for i in reversed(arr):
			ind = bisect_right(d, i)
			k.append(len(d) - ind)
			d.insert(ind, i)
		return list(reversed(k))


from bisect import bisect_left, insort_left

class Solution:

	def findSurpasser(self, arr, n):
		ret = [0 for _ in range(n)]
		h = [arr[-1]]
		for i in range(n - 2, -1, -1):
			x = bisect_left(h, arr[i])
			insort_left(h, arr[i])
			ret[i] = len(h) - x - 1
		return ret


class Solution:

	def findSurpasser(self, arr, n):
		gg = {elem: len(arr) - index - 1 for (index, elem) in enumerate(arr)}

		def sort(arr):
			if len(arr) < 2:
				return arr
			left = sort(arr[:len(arr) // 2])
			right = sort(arr[len(arr) // 2:])
			return merge(left, right)

		def merge(left, right):
			index_left = index_right = 0
			res = []
			while index_left < len(left) or index_right < len(right):
				if index_left == len(left):
					res.append(right[index_right])
					index_right += 1
				elif index_right == len(right):
					res.append(left[index_left])
					gg[left[index_left]] -= index_right
					index_left += 1
				elif left[index_left] < right[index_right]:
					res.append(left[index_left])
					gg[left[index_left]] -= index_right
					index_left += 1
				else:
					res.append(right[index_right])
					index_right += 1
			return res
		sort(arr)
		return [gg[elem] for elem in arr]


class Solution:

	def findSurpasser(self, arr, n):
		mp = {}
		for i in arr:
			mp[i] = 0
		original = [arr[i] for i in range(len(arr))]
		temp = [0 for i in range(len(arr))]
		merge_sort(arr, 0, len(arr) - 1, temp, mp)
		result = []
		for i in original:
			result.append(mp[i])
		return result

def merge_sort(arr, l, r, temp, mp):
	if l > r:
		return
	if l == r:
		return
	mid = (l + r) // 2
	merge_sort(arr, l, mid, temp, mp)
	merge_sort(arr, mid + 1, r, temp, mp)
	merge(arr, l, mid, r, temp, mp)

def merge(arr, l, mid, r, temp, mp):
	f = l
	s = mid + 1
	index = l
	while f <= mid and s <= r:
		if arr[f] < arr[s]:
			temp[index] = arr[f]
			mp[arr[f]] += r - s + 1
			f += 1
			index += 1
		else:
			temp[index] = arr[s]
			s += 1
			index += 1
	while f <= mid:
		temp[index] = arr[f]
		f += 1
		index += 1
	while s <= r:
		temp[index] = arr[s]
		s += 1
		index += 1
	for i in range(l, r + 1):
		arr[i] = temp[i]
	return


class Solution:

	def findSurpasser(self, arr, n):

		def sort(enum):
			half = len(enum) // 2
			if half:
				(left, right) = (sort(enum[:half]), sort(enum[half:]))
				(m, n) = (len(left), len(right))
				i = j = 0
				while i < m or j < n:
					if j == n or (i < m and left[i][1] <= right[j][1]):
						enum[i + j] = left[i]
						smaller[left[i][0]] += j
						i += 1
					else:
						enum[i + j] = right[j]
						j += 1
			return enum
		smaller = [0] * len(arr)
		sort(list(enumerate(arr)))
		offset = [n - i for i in range(n)]
		return [o - s - 1 for (o, s) in zip(offset, smaller)]


def merge(A, aux, low, mid, high, count):
	k = i = low
	j = mid + 1
	c = 0
	while i <= mid and j <= high:
		if A[i] > A[j]:
			count[A[i]] = count.get(A[i], 0) + c
			aux[k] = A[i]
			i = i + 1
		else:
			aux[k] = A[j]
			j = j + 1
			c = c + 1
		k = k + 1
	while i <= mid:
		count[A[i]] = count.get(A[i], 0) + c
		aux[k] = A[i]
		k = k + 1
		i = i + 1
	for i in range(low, high + 1):
		A[i] = aux[i]

def mergesort(A, aux, low, high, count):
	if high <= low:
		return
	mid = low + (high - low >> 1)
	mergesort(A, aux, low, mid, count)
	mergesort(A, aux, mid + 1, high, count)
	merge(A, aux, low, mid, high, count)

class Solution:

	def findSurpasser(self, A, n):
		count = {}
		aux = A.copy()
		A = A.copy()
		t = A + []
		mergesort(A, aux, 0, len(A) - 1, count)
		ans = []
		for i in range(len(t)):
			if t[i] not in count:
				ans.append(0)
			else:
				ans.append(count[t[i]])
		return ans


class Solution:

	def getInsertPos(self, arr, target):
		left = 0
		right = len(arr) - 1
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] < target:
				right = mid - 1
			else:
				left = mid + 1
		return left

	def findSurpasser(self, arr, n):
		res = []
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			pos = self.getInsertPos(stack, arr[i])
			res.append(pos)
			stack.insert(pos, arr[i])
		return res[::-1]


from bisect import bisect_right

class Solution:

	def findSurpasser(self, arr, n):
		sortedList = []
		ans = [0] * n
		for i in range(n - 1, -1, -1):
			pos = bisect_right(sortedList, arr[i])
			ln = len(sortedList)
			ans[i] = ln - pos
			sortedList.insert(pos, arr[i])
		return ans


def merge(arr, s, mid, e, surp):
	(i, j, k) = (s, mid, 0)
	a = [0] * (e - s)
	while i < mid and j < e:
		if arr[i] < arr[j]:
			surp[arr[i]] += e - j
			a[k] = arr[i]
			i += 1
		else:
			a[k] = arr[j]
			j += 1
		k += 1
	while i < mid:
		a[k] = arr[i]
		i += 1
		k += 1
	while j < e:
		a[k] = arr[j]
		j += 1
		k += 1
	k = 0
	for i in range(s, e):
		arr[i] = a[k]
		k += 1

def mergesort(arr, s, e, surp):
	if s >= e or s == e - 1:
		return
	mid = (s + e) // 2
	mergesort(arr, s, mid, surp)
	mergesort(arr, mid, e, surp)
	merge(arr, s, mid, e, surp)

class Solution:

	def findSurpasser(self, arr, n):
		surp = {}
		dup = arr[:]
		for x in arr:
			surp[x] = 0
		mergesort(arr, 0, n, surp)
		for i in range(n):
			dup[i] = surp[dup[i]]
		return dup


class Solution:

	def mergeSort(self, low, high, arr, indexes, count):
		if low >= high:
			return
		mid = (low + high) // 2
		self.mergeSort(low, mid, arr, indexes, count)
		self.mergeSort(mid + 1, high, arr, indexes, count)
		(lower_index, upper_index) = (low, mid + 1)
		new = []
		cnt = 0
		while lower_index < mid + 1 and upper_index < high + 1:
			if arr[indexes[lower_index]] < arr[indexes[upper_index]]:
				count[indexes[lower_index]] += cnt
				new.append(indexes[lower_index])
				lower_index += 1
			else:
				cnt += 1
				new.append(indexes[upper_index])
				upper_index += 1
		while lower_index < mid + 1:
			new.append(indexes[lower_index])
			count[indexes[lower_index]] += cnt
			lower_index += 1
		while upper_index < high + 1:
			new.append(indexes[upper_index])
			upper_index += 1
		for i in range(low, high + 1):
			indexes[i] = new[i - low]

	def findSurpasser(self, nums, n):
		n = len(nums)
		indexes = [i for i in range(n)]
		count = [0] * n
		self.mergeSort(0, n - 1, nums, indexes, count)
		for i in range(n):
			count[i] = n - i - 1 - count[i]
		return count