Given an array Arr of size N containing positive integers. Count number of smaller elements on right side of each array element.
Example 1:
Input:
N = 7
Arr[] = {12, 1, 2, 3, 0, 11, 4}
Output: 6 1 1 1 0 1 0
Explanation: There are 6 elements right
after 12. There are 1 element right after
1. And so on.
Example 2:
Input:
N = 5
Arr[] = {1, 2, 3, 4, 5}
Output: 0 0 0 0 0
Explanation: There are 0 elements right
after 1. There are 0 elements right after
2. And so on.
Your Task:
You don't need to read input or print anything. Your task is to complete the function constructLowerArray() which takes the array of integers arr and n as parameters and returns an array of integers denoting the answer.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}
0 ≤ Arr_{i  }≤ 10^{8}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:



	def constructLowerArray(self,arr, n):

		# code here

Solutions:
import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		(ans, temp) = ([], [])
		for i in range(n - 1, -1, -1):
			c = bisect.bisect_left(temp, arr[i])
			ans.append(c)
			temp.insert(c, arr[i])
		return ans[::-1]


class Solution:

	def merge(self, left, right):
		(i, j) = (0, 0)
		cnt = 0
		(m, n) = (len(left), len(right))
		sorted_arr = []
		while i < m and j < n:
			if left[i][1] > right[j][1]:
				cnt += 1
				sorted_arr.append(right[j])
				j += 1
			else:
				sorted_arr.append(left[i])
				self.ans[left[i][0]] += cnt
				i += 1
		while i < m:
			sorted_arr.append(left[i])
			self.ans[left[i][0]] += cnt
			i += 1
		while j < n:
			sorted_arr.append(right[j])
			cnt += 1
			j += 1
		return sorted_arr

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

	def constructLowerArray(self, arr, n):
		self.ans = [0 for _ in range(n)]
		nums = []
		for (i, num) in enumerate(arr):
			nums.append((i, num))
		sorted_arr = self.split(nums)
		return self.ans


class Solution:

	def constructLowerArray(self, arr, n):
		n = len(arr)
		result = [0] * n
		indices = [i for i in range(n)]

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

		def merge(low, mid, high):
			nonlocal indices
			nonlocal result
			left = low
			right = mid + 1
			temp = []
			while left <= mid and right <= high:
				if arr[indices[left]] <= arr[indices[right]]:
					temp.append(indices[left])
					result[indices[left]] += right - (mid + 1)
					left += 1
				else:
					temp.append(indices[right])
					right += 1
			while left <= mid:
				temp.append(indices[left])
				result[indices[left]] += right - (mid + 1)
				left += 1
			while right <= high:
				temp.append(indices[right])
				right += 1
			indices[low:high + 1] = temp
		mergesort(0, n - 1)
		return result


import bisect
from collections import namedtuple
Pair = namedtuple('Pair', ['value', 'index'])

class Solution:

	def constructLowerArray(self, arr, n):
		pairs = sorted([Pair(value, index) for (index, value) in enumerate(arr)], key=lambda p: (-p[0], -p[1]))
		indexs = []
		ans = [0] * n
		for (value, index) in pairs:
			right = n - index - 1
			i = bisect.bisect(indexs, index)
			big_right = len(indexs) - i
			ans[index] = right - big_right
			indexs.insert(i, index)
		return ans


from bisect import bisect_left

class Solution:

	def constructLowerArray(self, arr, n):
		ans = [0] * n
		sorted_arr = []
		for i in reversed(range(n)):
			a = arr[i]
			j = bisect_left(sorted_arr, a)
			ans[i] = j
			sorted_arr.insert(j, a)
		return ans


import bisect

class Solution:

	def constructLowerArray(self, arr, n):

		def merge(v, ans, l, mid, h):
			t = []
			i = l
			j = mid + 1
			while i < mid + 1 and j <= h:
				if v[i][0] > v[j][0]:
					ans[v[i][1]] += h - j + 1
					t.append(v[i])
					i += 1
				else:
					t.append(v[j])
					j += 1
			while i <= mid:
				t.append(v[i])
				i += 1
			while j <= h:
				t.append(v[j])
				j += 1
			k = 0
			i = l
			while i <= h:
				v[i] = t[k]
				i += 1
				k += 1

		def mergesort(v, ans, i, j):
			if i < j:
				mid = (i + j) // 2
				mergesort(v, ans, i, mid)
				mergesort(v, ans, mid + 1, j)
				merge(v, ans, i, mid, j)
		v = []
		for i in range(n):
			v.append([arr[i], i])
		ans = [0] * n
		mergesort(v, ans, 0, n - 1)
		return ans


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		an = sorted(arr)
		res = []
		for i in arr:
			p = bisect.bisect_left(an, i)
			res.append(p)
			del an[p]
		return res


class Solution:

	def constructLowerArray(self, nums, n):
		from bisect import bisect_left
		res = []
		sortedArr = []
		for num in nums[::-1]:
			idx = bisect_left(sortedArr, num)
			res.append(idx)
			sortedArr.insert(idx, num)
		return res[::-1]


class Solution:

	def constructLowerArray(self, arr, n):
		ans = [0 for i in range(len(arr))]
		for i in range(len(arr)):
			arr[i] = [arr[i], i]
		self.mergesort(arr, 0, len(arr) - 1, ans)
		return ans

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

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


class Solution:

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

	def divide(self, arr, l, r, ans):
		if l < r:
			mid = l + (r - l) // 2
			self.divide(arr, l, mid, ans)
			self.divide(arr, mid + 1, r, ans)
			self.merge(arr, l, mid, r, ans)
		else:
			return

	def constructLowerArray(self, arr, n):
		if n <= 1:
			return [0]
		ans = [0] * n
		li = []
		for i in range(n):
			li.append([arr[i], i])
		self.divide(li, 0, n - 1, ans)
		return ans


class Solution:

	def constructLowerArray(self, arr, n):
		from bisect import bisect_left
		ans = []
		w = []
		for i in range(n - 1, -1, -1):
			y = bisect_left(ans, arr[i])
			w += [y]
			ans.insert(y, arr[i])
		return w[::-1]


import bisect as bs

class Solution:

	def constructLowerArray(self, arr, n):
		lis = []
		temp = []
		for i in range(n - 1, -1, -1):
			k = bs.bisect_left(temp, arr[i])
			lis.append(k)
			temp.insert(k, arr[i])
		return lis[::-1]


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		(a, b) = ([], [])
		for i in range(n - 1, -1, -1):
			c = bisect.bisect_left(b, arr[i])
			a.append(c)
			b.insert(c, arr[i])
		return a[::-1]


from bisect import bisect_left

class Solution:

	def constructLowerArray(self, A, n):
		shadow = []
		ans = [0] * n
		for (i, v) in reversed(list(enumerate(A))):
			ins = bisect_left(shadow, v)
			shadow.insert(ins, v)
			ans[i] = ins
		return ans


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		s = []
		for i in range(n - 1, -1, -1):
			c = bisect.bisect_left(s, arr[i])
			bisect.insort(s, arr[i])
			arr[i] = c
		return arr


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		nums = arr
		n = len(nums)
		smallers = []
		for i in range(n - 1, -1, -1):
			currctr = bisect.bisect_left(smallers, nums[i])
			bisect.insort(smallers, nums[i])
			nums[i] = currctr
		return nums


from bisect import bisect_left

class Solution:

	def constructLowerArray(self, arr, n):
		counts = []
		new_arr = sorted(arr)
		for num in arr:
			counts.append(bisect_left(new_arr, num))
			new_arr.pop(counts[-1])
		return counts


from bisect import bisect_left as bl

class Solution:

	def constructLowerArray(self, arr, n):
		ans = []
		std = []
		for i in range(n - 1, -1, -1):
			ind = bl(std, arr[i])
			if ind == 0:
				ans.append(0)
			else:
				ans.append(ind)
			std.insert(ind, arr[i])
		ans.reverse()
		return ans


class Solution:
	d = dict()

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

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

	def constructLowerArray(self, arr, n):
		l = 0
		r = n - 1
		A = []
		for i in range(n):
			A.append([arr[i], i])
		for i in range(n):
			self.d[A[i][1]] = 0
		self.mergeSort(A, l, r)
		res = [0] * n
		for i in range(n):
			res[i] = self.d[i]
		return res


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		arr1 = sorted(arr)
		res = []
		for i in arr:
			ind = bisect.bisect_left(arr1, i)
			res.append(ind)
			del arr1[ind]
		return res


class FenwickTree:

	def __init__(self, n):
		self.tree = [0] * (n + 1)

	def update(self, index, delta=0):
		index += 1
		while 0 < index < len(self.tree):
			self.tree[index] += delta
			index += index & -index

	def getSumQuery(self, index):
		output = 0
		index += 1
		while index > 0:
			output += self.tree[index]
			index -= index & -index
		return output

class Solution:

	def constructLowerArray(self, nums, n):
		d = {e: i for (i, e) in enumerate(sorted(set(nums)))}
		indices = [d[num] for num in nums]
		tree = FenwickTree(len(indices))
		result = []
		for val in indices[::-1]:
			tree.update(val, 1)
			result.append(tree.getSumQuery(val - 1))
		return result[::-1]


class Solution:

	def constructLowerArray(self, arr, n):
		self.ans = [0] * n
		nums = []
		for (i, num) in enumerate(arr):
			nums.append([i, arr[i]])
		self.sort(nums)
		return self.ans

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

	def merge(self, left, right):
		res = []
		(l, r) = (0, 0)
		cnt = 0
		while l < len(left) and r < len(right):
			if left[l][1] > right[r][1]:
				res.append(right[r])
				cnt += 1
				r += 1
			else:
				res.append(left[l])
				self.ans[left[l][0]] += cnt
				l += 1
		while l < len(left):
			res.append(left[l])
			self.ans[left[l][0]] += cnt
			l += 1
		while r < len(right):
			res.append(right[r])
			r += 1
		return res


class SegmentTree:

	def __init__(self, n):
		self.N = n
		self.BIT = [0] * (2 * n)

	def update(self, idx):
		n = self.N
		A = self.BIT
		idx += n
		A[idx] += 1
		while idx > 1:
			A[idx >> 1] = A[idx] + A[idx ^ 1]
			idx >>= 1

	def query(self, l, r):
		n = self.N
		A = self.BIT
		l += n
		r += n
		res = 0
		while l <= r:
			if l & 1:
				res += A[l]
				l += 1
			if r & 1 == 0:
				res += A[r]
				r -= 1
			l >>= 1
			r >>= 1
		return res

class Solution:

	def constructLowerArray(self, A, N):
		tree = SegmentTree(N)
		mp = {}
		for i in A:
			mp[i] = 1
		P = []
		ans = []
		c = -1
		for i in sorted(mp):
			c += 1
			mp[i] = c
		for i in A:
			P.append(mp[i])
		for i in range(N - 1, -1, -1):
			ans.append(tree.query(0, P[i] - 1))
			tree.update(P[i])
		return ans[::-1]


class Solution:

	def constructLowerArray(self, arr, n):
		ans = [0] * n
		m_arr = []
		for i in range(n):
			m_arr.append((arr[i], i))
		self.mergesort(m_arr, ans, 0, n - 1)
		return ans

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

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


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		items = [arr[-1]]
		result = [0]
		for i in range(1, n):
			item = arr[-i - 1]
			index = bisect.bisect_left(items, item)
			items.insert(index, item)
			result.append(index)
		return list(reversed(result))


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		list1 = [arr[-1]]
		arr2 = [0]
		maximum = arr[-1]
		minimum = arr[-1]
		for i in range(-2, -n - 1, -1):
			if arr[i] > maximum:
				maximum = arr[i]
				arr2.append(-i - 1)
				bisect.insort(list1, arr[i])
			elif arr[i] < minimum:
				minimum = arr[i]
				arr2.append(0)
				bisect.insort(list1, arr[i])
			else:
				bisect.insort(list1, arr[i])
				value = bisect.bisect_left(list1, arr[i])
				arr2.append(value)
		return arr2[::-1]


from sortedcontainers import SortedList

class Solution:

	def constructLowerArray(self, arr, n):
		l = []
		sorted_arr = SortedList(arr)
		for i in arr:
			s = sorted_arr.index(i)
			l.append(s)
			sorted_arr.remove(i)
		return l


from sortedcontainers import SortedList

class Solution:

	def constructLowerArray(self, arr, n):
		l = []
		sorted_arr = SortedList(arr)
		for i in arr:
			s = sorted_arr.index(i)
			l.append(s)
			sorted_arr.remove(i)
		return l
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		st = []
		res = [0 for i in range(n)]
		for i in range(n - 1, -1, -1):
			x = bisect.bisect_left(st, arr[i])
			res[i] = x
			st.insert(x, arr[i])
		return res


import bisect

class Solution:

	def constructLowerArray(self, arr, n):
		a = sorted(arr)
		res = []
		for i in arr:
			x = bisect.bisect_left(a, i)
			res.append(x)
			del a[x]
		return res


from sortedcontainers import SortedList

class Solution:

	def constructLowerArray(self, nums, n):
		res = []
		sorted_nums = SortedList(nums)
		for e in nums:
			idx = sorted_nums.index(e)
			res.append(idx)
			sorted_nums.remove(e)
		return res


class Solution:

	def constructLowerArray(self, arr, n):
		marr = []
		temp = []
		for i in range(0, n):
			marr.append((arr[i], i))
			temp.append((arr[i], i))
		count = [0] * n

		def inv(marr, temp, start, end):
			if start >= end:
				return
			mid = (start + end) // 2
			inv(marr, temp, start, mid)
			inv(marr, temp, mid + 1, end)
			merge(marr, temp, start, mid, end)

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


class Solution:

	def constructLowerArray(self, arr, n):
		self.answer = [0] * n
		self.divide([[num, i] for (i, num) in enumerate(arr)])
		return self.answer

	def divide(self, numbers):
		return numbers if len(numbers) == 1 else self.conqure(self.divide(numbers[:len(numbers) // 2]), self.divide(numbers[len(numbers) // 2:]))

	def conqure(self, numbers1, numbers2):
		numbers = []
		n = len(numbers1)
		m = len(numbers2)
		i = j = 0
		while i < n and j < m:
			if numbers1[i][0] <= numbers2[j][0]:
				numbers.append(numbers1[i])
				self.answer[numbers1[i][1]] += j
				i += 1
			else:
				numbers.append(numbers2[j])
				j += 1
		while i < n:
			numbers.append(numbers1[i])
			self.answer[numbers1[i][1]] += m
			i += 1
		while j < m:
			numbers.append(numbers2[j])
			j += 1
		return numbers