A knockout tournament is going on. A total of N number of players are participating. Each match will have two players. Every player has a distinct rating associated with him. The player with the more rating wins in a match. In one round, the 1st player will play a match against 2nd player, 3rd player will play a match against 4th player and so on. If there is odd number of players, last one will qualify to the next round without playing a match. Since it is a knockout tournament, whoever loses a match leaves the tournament. Rating of each player is unique.
Your task is to find out the number of matches each player wins in the tournament. The tournament ends when there is only one player remaining in the end.
 
Example 1:
Input:
N = 5
A[] = {7, 1, 5, 3, 9}
Output:
3 1 2 1 1
Explanation:
players: 7 1 5 3 9
The first round: (7 has a match with 1),
(5 has a match with 3), (9 has no matches
automatically qualifies)
players: 7 5 9
The second round: (7 has a match with 5),
(9 has no matches automatically qualifies)
players: 7 9
The third round: (7 has a match with 9).
The player with rating 7 played 3 matches. 
The player with rating 1 played 1 match. 
The player with rating 5 played 2 matches.
The player with rating 3 played 1 match.  
The player with rating 9 played 1 match.
 
Example 2:
Input:
N = 6
A[] = {8, 4, 3, 5, 2, 6}
Output:
3 1 1 2 1 2 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function getAnswer() which takes the array A[] and its size N as inputs and stores the number of wins of each player in the answer[] array.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5  }
0 ≤ rating of player ≤ 10^{6}
The rating of the players will be distinct.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def getAnswer(self, arr, answer, n):
        #  Your task is to store the answer of each index in the 'answer' array
        #  Note: indexing is 0 based

Solutions:
class Solution:

	def getAnswer(self, arr, answer, n):
		lis = arr.copy()
		dic = {}
		for i in arr:
			dic[i] = 1
		if n % 2 != 0:
			dic[arr[-1]] = 0
		while len(lis) > 1:
			j = 0
			mis = []
			while j + 1 < len(lis):
				if lis[j] < lis[j + 1]:
					mis.append(lis[j + 1])
				else:
					mis.append(lis[j])
				j += 2
			if len(lis) % 2 != 0:
				mis.append(lis[-1])
			lis = mis
			if len(lis) % 2 != 0:
				dic[lis[-1]] -= 1
			for i in lis:
				if i in dic:
					dic[i] += 1
		for i in range(n):
			answer[i] = dic[arr[i]]
		return answer


class Solution:

	def getAnswer(self, arr, answer, n):
		x = dict()
		for i in arr:
			x[i] = 0
		copy = arr
		while len(arr) != 1:
			temp = []
			for i in range(0, len(arr) - 1, 2):
				temp.append(max(arr[i], arr[i + 1]))
				x[arr[i]] += 1
				x[arr[i + 1]] += 1
			if len(arr) % 2 == 1:
				temp.append(arr[-1])
			arr = temp
		j = 0
		for i in copy:
			answer[j] = x[i]
			j += 1

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		answer = [0 for i in range(n)]
		ob = Solution()
		ob.getAnswer(arr, answer, n)
		print(*answer)
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def getAnswer(self, arr, answer, n):
		a = [[0 for i in range(2)] for j in range(n + 5)]
		for i in range(1, n + 1):
			a[i][0] = arr[i - 1]
			a[i][1] = i
		count = n
		while count > 1:
			p = 1
			for i in range(1, count, 2):
				answer[a[i][1] - 1] += 1
				answer[a[i + 1][1] - 1] += 1
				if a[i][0] > a[i + 1][0]:
					a[p][0] = a[i][0]
					a[p][1] = a[i][1]
					p += 1
				elif a[i + 1][0] > a[i][0]:
					a[p][0] = a[i + 1][0]
					a[p][1] = a[i + 1][1]
					p += 1
			if count % 2 == 1:
				a[count // 2 + 1][0] = a[count][0]
				a[count // 2 + 1][1] = a[count][1]
				count = count // 2 + 1
			elif count % 2 == 0:
				count = count // 2


class Solution:

	def getAnswer1(self, arr, answer, max):
		new_max = []
		for index in range(0, len(max), 2):
			i = max[index]
			if index + 1 < len(max):
				j = max[index + 1]
				answer[i] += 1
				answer[j] += 1
				if arr[i] > arr[j]:
					new_max.append(i)
				else:
					new_max.append(j)
			else:
				new_max.append(i)
		if len(new_max) >= 2:
			ob = Solution()
			ob.getAnswer1(arr, answer, new_max)
		else:
			return answer

	def getAnswer(self, arr, answer, n):
		max = []
		for i in range(0, n, 2):
			if i + 1 < n:
				answer[i] += 1
				answer[i + 1] += 1
				if arr[i] > arr[i + 1]:
					max.append(i)
				else:
					max.append(i + 1)
			else:
				max.append(i)
		if len(max) >= 2:
			ob = Solution()
			ob.getAnswer1(arr, answer, max)