Given an array arr[ ] of n integers, for every element, find the closest element on it's right that has a greater frequency than its own frequency.
Frequency is the number of times the element appears in the array.
 
Example 1:
Input:
n = 6
arr[] = {2 1 1 3 2 1}
Output:
1 -1 -1 2 1 -1 
Explanation:
1 appears 3 times.
2 appears 2 times.
3 appears 1 time. 
For arr[0] ie, 2
arr[1] ie 1 is the closest element on its 
right which has greater frequency than the 
frequency of 2. For the arr[1] and arr[2] no element 
on the right has greater frequency than 1, 
so -1 will be printed. and so on. 
Example 2:
Input:
n = 10
arr[] = {5 1 2 3 2 5 5 4 5 2}
Output:
-1 2 5 2 5 -1 -1 5 -1 -1
 
Your task:
Your task is to complete the function print_next_greater_freq() which take two parameters arr and n.This function returns answer(as a list of integers) as explained above.
Expected time complexity: O(n)
Expected space complexity: O(n)
Constraints:
1 <= n <= 10^{4}
1 <= arr[i] <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: class Solution:
    def print_next_greater_freq(self,arr,n):
        # code here


Solutions:
class Solution:

	def print_next_greater_freq(self, arr, n):
		stack = []
		res = [-1] * n
		freq = {}
		for i in arr:
			if i not in freq:
				freq[i] = 1
			else:
				freq[i] += 1
		for i in range(n):
			while stack and freq[arr[stack[-1]]] < freq[arr[i]]:
				res[stack.pop()] = arr[i]
			stack.append(i)
		return res


class Solution:

	def print_next_greater_freq(self, arr, n):
		from collections import Counter
		a = []
		s = []
		d = Counter(arr)
		for i in range(n - 1, -1, -1):
			while s and d[arr[s[-1]]] <= d[arr[i]]:
				s.pop()
			if s:
				a.append(arr[s[-1]])
			else:
				a.append(-1)
			s.append(i)
		a[:] = a[::-1]
		return a


from collections import defaultdict

class Solution:

	def print_next_greater_freq(self, arr, n):
		freq = defaultdict(int)
		for a in arr:
			freq[a] += 1
		st = []
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			while len(st) > 0 and freq[st[-1]] <= freq[arr[i]]:
				st.pop()
			if len(st) == 0:
				ans[i] = -1
			else:
				ans[i] = st[-1]
			st.append(arr[i])
		return ans


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		h = {}
		for i in arr:
			if i in h:
				h[i] += 1
			else:
				h[i] = 1
		stack = []
		ans = []
		for i in range(n - 1, -1, -1):
			if len(stack) == 0:
				ans.append(-1)
			elif len(stack) > 0 and h[arr[i]] < h[stack[-1]]:
				ans.append(stack[-1])
			elif len(stack) > 0 and h[arr[i]] >= h[stack[-1]]:
				while len(stack) > 0 and h[arr[i]] >= h[stack[-1]]:
					stack.pop()
				if len(stack) == 0:
					ans.append(-1)
				else:
					ans.append(stack[-1])
			stack.append(arr[i])
		return ans[::-1]


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		h = Counter(arr)
		s = []
		res = []
		for i in range(n - 1, -1, -1):
			while len(s) != 0 and h[arr[i]] >= h[s[-1]]:
				s.pop()
			if len(s) == 0:
				res.append(-1)
			else:
				res.append(s[-1])
			s.append(arr[i])
		return res[::-1]


import collections

class Solution:

	def print_next_greater_freq(self, arr, n):
		mp = collections.Counter(arr)
		ans = []
		stack = []
		for i in range(n - 1, -1, -1):
			if not stack:
				ans.append(-1)
			elif stack and mp[stack[-1]] > mp[arr[i]]:
				ans.append(stack[-1])
			else:
				while stack and mp[arr[i]] >= mp[stack[-1]]:
					stack.pop()
				if not stack:
					ans.append(-1)
				else:
					ans.append(stack[-1])
			stack.append(arr[i])
		ans.reverse()
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		n = len(arr)
		st = [arr[n - 1]]
		ans = [-1]
		for i in range(n - 2, -1, -1):
			while st and d[st[-1]] <= d[arr[i]]:
				st.pop()
			if st == []:
				ans.append(-1)
			else:
				ans.append(st[-1])
			st.append(arr[i])
		return ans[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		freq = {}
		for i in arr:
			if i not in freq:
				freq[i] = 0
			freq[i] += 1
		stack = [(arr[-1], freq[arr[-1]])]
		ans = [-1 for i in range(n)]
		for j in range(n - 2, -1, -1):
			while stack and freq[arr[j]] >= freq[stack[-1][0]]:
				stack.pop()
			if stack:
				ans[j] = stack[-1][0]
			stack.append((arr[j], freq[arr[j]]))
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		dic = {}
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
		stk = []
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			if len(stk) == 0:
				ans[i] = -1
			elif stk and dic[stk[-1]] > dic[arr[i]] and (stk[-1] != arr[i]):
				ans[i] = stk[-1]
			elif dic[stk[-1]] <= dic[arr[i]]:
				while stk and dic[stk[-1]] <= dic[arr[i]]:
					stk.pop()
				if stk:
					ans[i] = stk[-1]
			stk.append(arr[i])
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		dic = {}
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		stack = []
		ans = []
		for i in range(n - 1, -1, -1):
			(cur_ele, curF) = (arr[i], dic[arr[i]])
			while stack and stack[-1][1] <= curF:
				stack.pop()
			if not stack:
				ans.append(-1)
			else:
				ans.append(stack[-1][0])
			stack.append((cur_ele, curF))
		return ans[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		mp = {}
		for i in arr:
			if i not in mp:
				mp[i] = 1
			else:
				mp[i] += 1
		st = []
		ans = []
		for i in range(n - 1, -1, -1):
			if len(st) == 0:
				ans.append(-1)
			elif mp[arr[i]] < mp[st[-1]]:
				ans.append(st[-1])
			else:
				while len(st) > 0 and mp[arr[i]] >= mp[st[-1]]:
					st.pop()
				if len(st) == 0:
					ans.append(-1)
				else:
					ans.append(st[-1])
			st.append(arr[i])
		return ans[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for ele in arr:
			if ele in d:
				d[ele] += 1
			else:
				d[ele] = 1
		st = []
		res = []
		for i in range(n - 1, -1, -1):
			if st == []:
				st.append(arr[i])
				res.append(-1)
			elif d[arr[i]] < d[st[-1]]:
				res.append(st[-1])
				st.append(arr[i])
			else:
				while st and d[arr[i]] >= d[st[-1]]:
					st.pop()
				if st == []:
					res.append(-1)
				else:
					res.append(st[-1])
				st.append(arr[i])
		return res[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = dict()
		out = [0] * n
		for i in arr:
			if i not in d:
				d[i] = 0
			else:
				d[i] += 1
		st = []
		for i in range(n):
			if len(st) == 0:
				st.append(i)
			else:
				while st and d[arr[st[-1]]] < d[arr[i]]:
					out[st.pop()] = arr[i]
				st.append(i)
		if st:
			while st:
				out[st.pop()] = -1
		return out


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		c = Counter(arr)
		stack = []
		result = [-1] * n
		for i in range(n):
			while stack and c[arr[i]] > stack[-1][1]:
				result[stack.pop()[0]] = arr[i]
			stack.append((i, c[arr[i]]))
		return result


class Solution:

	def print_next_greater_freq(self, arr, n):
		freq = {}
		s = []
		ans = [-1] * n
		for i in range(n):
			if arr[i] in freq:
				freq[arr[i]] += 1
			else:
				freq[arr[i]] = 1
		for i in range(n - 1, -1, -1):
			while s and freq[s[-1]] <= freq[arr[i]]:
				s.pop()
			if s:
				ans[i] = s[-1]
			s.append(arr[i])
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		dic = {}
		lis = []
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		stack = []
		for i in arr[::-1]:
			if len(stack) == 0:
				lis.append(-1)
			if stack:
				if dic[stack[-1]] <= dic[i]:
					while dic[stack[-1]] <= dic[i]:
						stack.pop()
						if len(stack) == 0:
							lis.append(-1)
							break
				if stack:
					if dic[stack[-1]] > dic[i]:
						lis.append(stack[-1])
			stack.append(i)
		return lis[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = dict()
		for x in arr:
			if d.get(x) == None:
				d[x] = 1
			else:
				d[x] += 1
		stack = list()
		ans = []
		for x in arr[::-1]:
			if not stack:
				ans.append(-1)
			else:
				while stack:
					if d[stack[-1]] > d[x]:
						break
					stack.pop()
				if not stack:
					ans.append(-1)
				else:
					ans.append(stack[-1])
			stack.append(x)
		return ans[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		stack = []
		f = []
		for x in arr:
			if d.get(x) == None:
				d[x] = 1
			else:
				d[x] += 1
		while arr:
			cur = arr.pop()
			i = 0
			if len(stack) == 0:
				f.append(-1)
				stack.append(cur)
				i = 1
			while stack and i == 0:
				if d[stack[-1]] > d[cur] and stack[-1] != cur:
					f.append(stack[-1])
					stack.append(cur)
					break
				else:
					stack.pop()
					if len(stack) == 0:
						f.append(-1)
						stack.append(cur)
						break
		return f[::-1]


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		c = Counter(arr)
		stack = []
		result = []
		for item in arr[::-1]:
			while stack and c[item] >= c[stack[-1]]:
				stack.pop()
			if stack:
				result.append(stack[-1])
			else:
				result.append(-1)
			stack.append(item)
		return result[::-1]


import collections

class Solution:

	def print_next_greater_freq(self, arr, n):
		res = [-1] * n
		mapp = collections.Counter(arr)
		temp = []
		for (idx, val) in enumerate(arr):
			if not temp:
				temp.append(idx)
			else:
				curr = mapp[val]
				while temp:
					prev_idx = temp[-1]
					prev_freq = mapp[arr[prev_idx]]
					if prev_freq < curr:
						res[prev_idx] = val
						temp = temp[:len(temp) - 1]
					else:
						break
				temp.append(idx)
		return res


class Solution:

	def print_next_greater_freq(self, arr, n):
		st = []
		l = []
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		i = n - 1
		while i >= 0:
			if len(st) == 0:
				l.append(-1)
				st.append(arr[i])
				i -= 1
			elif d[st[-1]] > d[arr[i]]:
				l.append(st[-1])
				st.append(arr[i])
				i -= 1
			else:
				while st and d[st[-1]] <= d[arr[i]]:
					st.pop(-1)
		return l[::-1]


class Solution:

	def print_next_greater_freq(self, a, n):
		d = {}
		stack = []
		for i in a:
			d[i] = d.get(i, 0) + 1
		i = n - 1
		b = []
		while i >= 0:
			if len(stack) != 0:
				if d[stack[-1]] > d[a[i]]:
					b.append(stack[-1])
					stack.append(a[i])
					i = i - 1
				else:
					stack.pop()
			else:
				stack.append(a[i])
				b.append(-1)
				i = i - 1
		return b[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		s = []
		ans = [-1 for i in range(len(arr))]
		for i in range(len(arr)):
			while len(s) != 0 and s[-1][1] < d[arr[i]]:
				(node, fre, pos) = s.pop()
				ans[pos] = arr[i]
			s.append([arr[i], d[arr[i]], i])
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		stack = [[0, d[arr[0]]]]
		res = [-1] * n
		for i in range(1, n):
			if len(stack) == 0 or stack[-1][1] >= d[arr[i]]:
				stack.append([i, d[arr[i]]])
			else:
				while stack and stack[-1][1] < d[arr[i]]:
					res[stack[-1][0]] = arr[i]
					stack.pop()
				stack.append([i, d[arr[i]]])
		return res


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		a = arr
		d = dict(Counter(a))
		answer = [-1] * len(a)
		s = []
		a = a[::-1]
		for i in range(len(a)):
			while len(s) > 0 and d[a[i]] >= d[s[-1]]:
				s.pop(-1)
			if len(s) > 0:
				answer[i] = s[-1]
			s += [a[i]]
		return answer[::-1]


from collections import deque

class Solution:

	def print_next_greater_freq(self, arr, n):
		freq_arr = dict()
		freq_idx = dict()
		for num in arr:
			if num in freq_arr:
				freq_arr[num] += 1
			else:
				freq_arr[num] = 1
		for i in range(n):
			if arr[i] in freq_idx:
				freq_idx[arr[i]].append(i)
			else:
				freq_idx[arr[i]] = []
				freq_idx[arr[i]].append(i)
		stack = deque()
		output = [-1 for i in range(n)]
		stack.append(arr[0])
		for i in range(1, n):
			if len(stack) != 0:
				while freq_arr[arr[i]] > freq_arr[stack[-1]]:
					v = stack.pop()
					output[freq_idx[v][0]] = arr[i]
					freq_idx[v].pop(0)
					if len(stack) == 0:
						break
			stack.append(arr[i])
		return output


class Solution:

	def print_next_greater_freq(self, arr, n):
		dict = {}
		for i in arr:
			if i not in dict:
				dict[i] = 1
			else:
				dict[i] += 1
		stack = []
		result = []
		for i in range(n - 1, -1, -1):
			while stack and stack[-2] <= dict[arr[i]]:
				stack.pop()
				stack.pop()
			if stack == []:
				result.append(-1)
			else:
				result.append(stack[-1])
			stack.append(dict[arr[i]])
			stack.append(arr[i])
		return result[::-1]


class Solution:

	def print_next_greater_freq(self, a, n):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		s = []
		o = []
		for i in range(n - 1, -1, -1):
			while s and d[s[-1]] <= d[a[i]]:
				s.pop()
			if s:
				o.append(s[-1])
			else:
				o.append(-1)
			s.append(a[i])
		o.reverse()
		return o


class Solution:

	def print_next_greater_freq(self, arr, n):
		dory = {}
		for j in arr:
			if j in dory:
				dory[j] += 1
			else:
				dory[j] = 1
		res = [-1] * n
		stack = []
		for i in range(n):
			temp = dory[arr[i]]
			while len(stack):
				if temp > dory[arr[stack[-1]]]:
					res[stack[-1]] = arr[i]
					stack.pop()
				else:
					break
			stack.append(i)
		return res


class Solution:

	def print_next_greater_freq(self, a, n):
		s = []
		b = []
		m = {}
		for i in arr:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		for i in range(n - 1, -1, -1):
			c = []
			while len(s) != 0 and m[s[-1]] <= m[arr[i]]:
				s.pop()
			if len(s) == 0:
				b.append(-1)
			else:
				b.append(s[-1])
			s.append(arr[i])
		return b[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		dic = {}
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		stack = []
		l = []
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				l.append(-1)
			elif dic[arr[i + 1]] > dic[arr[i]]:
				l.append(arr[i + 1])
			else:
				while len(stack) != 0 and dic[stack[-1]] <= dic[arr[i]]:
					stack.pop()
				if len(stack) == 0:
					l.append(-1)
				else:
					l.append(stack[-1])
			stack.append(arr[i])
		return l[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in range(n):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
		st = []
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			while st and d[st[-1]] <= d[arr[i]]:
				st.pop()
			if not st:
				ans[i] = -1
			else:
				ans[i] = st[-1]
			st.append(arr[i])
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		result = []
		stack = []
		h = {}
		for i in arr:
			if i in h:
				h[i] += 1
			else:
				h[i] = 1
		for i in range(n - 1, -1, -1):
			if len(stack) == 0:
				result.append(-1)
			elif len(stack) > 0 and h[stack[-1]] > h[arr[i]]:
				result.append(stack[-1])
			elif len(stack) > 0 and h[stack[-1]] <= h[arr[i]]:
				while len(stack) > 0 and h[stack[-1]] <= h[arr[i]]:
					stack.pop()
				if len(stack) == 0:
					result.append(-1)
				else:
					result.append(stack[-1])
			stack.append(arr[i])
		return result[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		x = []
		ans = []
		x.append(arr[-1])
		ans.append(-1)
		arr = arr[::-1]
		for i in arr[1:]:
			while len(x) > 0 and d[i] + 1 > d[x[-1]]:
				x.pop()
			if len(x) == 0:
				ans.append(-1)
			else:
				ans.append(x[-1])
			x.append(i)
		return ans[::-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		ans = obj.print_next_greater_freq(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def print_next_greater_freq(self, arr, n):
		limit = int(10000.0) + 1
		freq = [0] * limit
		n = len(arr)
		st = []
		for i in range(n):
			freq[arr[i]] += 1
		res = [-1] * n
		for i in range(n):
			while st and freq[arr[st[-1]]] < freq[arr[i]]:
				res[st.pop()] = arr[i]
			st.append(i)
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		ans = obj.print_next_greater_freq(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		stack = []
		lst = []
		for num in arr:
			if num not in d:
				d[num] = 1
			else:
				d[num] += 1
		for i in range(n - 1, -1, -1):
			while len(stack) != 0 and d[arr[i]] >= d[stack[-1]]:
				stack.pop()
			if len(stack) == 0:
				lst.append(-1)
			else:
				lst.append(stack[-1])
			stack.append(arr[i])
		return lst[::-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		ans = obj.print_next_greater_freq(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def print_next_greater_freq(self, arr, n):
		map = {}
		for i in range(n):
			if arr[i] in map:
				map[arr[i]] += 1
			else:
				map[arr[i]] = 1
		stack = []
		ans = [-1] * n
		ans[n - 1] = -1
		crnt = map[arr[n - 1]]
		stack.append([arr[n - 1], crnt])
		for i in range(n - 2, -1, -1):
			crnt = map[arr[i]]
			while stack and crnt >= stack[-1][1]:
				stack.pop()
			if not stack:
				ans[i] = -1
			else:
				ans[i] = stack[-1][0]
			stack.append([arr[i], map[arr[i]]])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		ans = obj.print_next_greater_freq(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		l = []
		s = [arr[-1]]
		for i in range(n - 2, -1, -1):
			while d[arr[i]] >= d[s[-1]]:
				s.pop()
				if s == []:
					break
			if s == []:
				l.append(-1)
			else:
				l.append(s[-1])
			s.append(arr[i])
		return l[::-1] + [-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		ans = obj.print_next_greater_freq(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def print_next_greater_freq(self, arr, n):
		freq = []
		hm = {}
		for i in range(n):
			if hm.get(arr[i]):
				hm[arr[i]] += 1
			else:
				hm[arr[i]] = 1
		for i in range(n):
			freq.append(hm[arr[i]])
		brr = []
		s = []
		st = []
		for i in range(n):
			while s:
				if freq[n - i - 1] < s[len(s) - 1]:
					brr.append(arr[st[len(s) - 1]])
					break
				s.pop()
				st.pop()
			if not s:
				brr.append(-1)
			s.append(freq[n - i - 1])
			st.append(n - i - 1)
		brr.reverse()
		return brr
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		ans = obj.print_next_greater_freq(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		gg = Counter(arr)
		ans = [-1 for i in range(n)]
		stack = [arr[-1]]
		for i in range(n - 2, -1, -1):
			while len(stack) != 0 and gg[arr[i]] >= gg[stack[-1]]:
				stack.pop()
			if len(stack) != 0:
				ans[i] = stack[-1]
			stack.append(arr[i])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		ans = obj.print_next_greater_freq(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def print_next_greater_freq(self, arr, n):
		m = {}
		for i in arr:
			if i in m:
				m[i] = m[i] + 1
			else:
				m[i] = 1
		ans = [-1] * n
		s = [0]
		curr = arr[0]
		for i in range(1, n):
			if m[arr[i]] <= m[curr]:
				s.append(i)
				curr = arr[i]
			else:
				while m[arr[s[-1]]] < m[arr[i]]:
					b = s.pop()
					ans[b] = arr[i]
					if len(s) == 0:
						break
				s.append(i)
				curr = arr[i]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		ans = obj.print_next_greater_freq(arr, n)
		for i in ans:
			print(i, end=' ')
		print()


class Solution:

	def print_next_greater_freq(self, arr, n):
		hashTable = {}
		for i in arr:
			if i in hashTable:
				hashTable[i] += 1
			else:
				hashTable[i] = 1
		answer = [0 for i in range(n)]
		stack = [0] * n
		top = -1
		top += 1
		stack[top] = 0
		for i in range(1, n):
			if hashTable[arr[i]] < hashTable[arr[stack[top]]]:
				top += 1
				stack[top] = i
			else:
				while top > -1 and hashTable[arr[i]] > hashTable[arr[stack[top]]]:
					answer[stack[top]] = arr[i]
					top -= 1
				top += 1
				stack[top] = i
		for i in range(n):
			if answer[i] == 0:
				answer[i] = -1
		return answer


class Solution:

	def print_next_greater_freq(self, arr, n):
		from collections import OrderedDict
		x = OrderedDict.fromkeys(arr, 0)
		for i in arr:
			x[i] += 1
		s = []
		res = []
		for i in range(n - 1, -1, -1):
			while len(s) != 0 and x[arr[i]] >= x[s[-1]]:
				s.pop()
			if len(s) == 0:
				res.append(-1)
			else:
				res.append(s[-1])
			s.append(arr[i])
		res = res[::-1]
		return res


class Solution:

	def print_next_greater_freq(self, arr, n):
		m = {}
		for i in arr:
			if i in m:
				m[i] = m[i] + 1
			else:
				m[i] = 1
		ans = [-1] * n
		s = [0]
		curr = arr[0]
		for i in range(1, n):
			if m[arr[i]] <= m[curr]:
				s.append(i)
				curr = arr[i]
			else:
				while m[arr[s[-1]]] < m[arr[i]]:
					b = s.pop()
					ans[b] = arr[i]
					if len(s) == 0:
						break
				s.append(i)
				curr = arr[i]
		return ans


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		mp = Counter(arr)
		s = []
		l = []
		for i in range(n - 1, -1, -1):
			if s == []:
				l.append(-1)
			elif mp[arr[i]] < s[-1][1]:
				l.append(s[-1][0])
			else:
				while len(s) > 0 and mp[arr[i]] >= s[-1][1]:
					s.pop()
				if len(s) == 0:
					l.append(-1)
				else:
					l.append(s[-1][0])
			s.append([arr[i], mp[arr[i]]])
		l = l[::-1]
		return l


class Solution:

	def FreqArr(self, arr):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		return d

	def print_next_greater_freq(self, arr, n):
		d = self.FreqArr(arr)
		stk = []
		result = []
		for i in range(len(arr) - 1, -1, -1):
			if len(stk) == 0:
				result.append(-1)
			elif d[stk[-1]] > d[arr[i]]:
				result.append(stk[-1])
			elif d[stk[-1]] <= d[arr[i]]:
				while stk and d[stk[-1]] <= d[arr[i]]:
					stk.pop()
				if len(stk) == 0:
					result.append(-1)
				else:
					result.append(stk[-1])
			stk.append(arr[i])
		result.reverse()
		return result


class Solution:

	def print_next_greater_freq(self, a, n):
		dict = {}
		stk = []
		ans = []
		for i in range(n):
			if a[i] in dict.keys():
				dict[a[i]] += 1
			else:
				dict[a[i]] = 1
		for i in range(n - 1, -1, -1):
			while len(stk) != 0 and dict[a[i]] >= dict[stk[-1]]:
				stk.pop()
			if len(stk) == 0:
				ans.append(-1)
			else:
				ans.append(stk[-1])
			stk.append(a[i])
		ans = ans[::-1]
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		stack = []
		sl = 0
		ans = [-1 for i in range(n)]
		for i in range(n - 1, -1, -1):
			c1 = d[arr[i]]
			while sl > 0 and (not stack[sl - 1][1] > c1):
				stack.pop()
				sl -= 1
			if sl != 0:
				ans[i] = stack[sl - 1][0]
			stack.append([arr[i], c1])
			sl += 1
		return ans


class Solution:

	def next_g(self, arr, n):
		stack = []
		ans = [-1] * n
		for i in range(n - 1, -1, -1):
			while stack != [] and arr[stack[-1]] <= arr[i]:
				stack.pop()
			if stack != []:
				ans[i] = stack[-1]
			stack.append(i)
		return ans

	def print_next_greater_freq(self, arr, n):
		d = {}
		out = []
		for i in arr:
			d[i] = d.get(i, 0) + 1
		freq = []
		for i in range(n):
			freq.append(d[arr[i]])
		nf_ind = self.next_g(freq, n)
		for i in nf_ind:
			if i == -1:
				out.append(-1)
			else:
				out.append(arr[i])
		return out


class Solution:

	def print_next_greater_freq(self, arr, n):
		stack = [arr[-1]]
		ngf = [-1]
		f = {}
		for element in arr:
			if element not in f:
				f[element] = 1
			else:
				f[element] += 1
		for i in range(len(arr) - 2, -1, -1):
			if f[arr[i]] < f[stack[-1]]:
				ngf.append(stack[-1])
				stack.append(arr[i])
			elif f[arr[i]] >= f[stack[-1]]:
				while len(stack) != 0 and f[arr[i]] >= f[stack[-1]]:
					stack.pop()
				if len(stack) == 0:
					ngf.append(-1)
					stack.append(arr[i])
				else:
					ngf.append(stack[-1])
					stack.append(arr[i])
		ngf = ngf[::-1]
		return ngf


from collections import defaultdict as dd

class Solution:

	def print_next_greater_freq(self, arr, n):
		map = dd(int)
		for el in arr:
			map[el] += 1
		stack = []
		ans = []
		for i in range(n - 1, -1, -1):
			el = arr[i]
			freq = map[el]
			if not stack:
				stack.append(el)
				ans.append(-1)
			elif freq < map[stack[-1]]:
				ans.append(stack[-1])
				stack.append(el)
			else:
				while stack and map[stack[-1]] <= freq:
					stack.pop()
				if stack:
					ans.append(stack[-1])
					stack.append(el)
				else:
					ans.append(-1)
					stack.append(el)
		return ans[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		s = []
		r = []
		for i in arr:
			d[i] = d.get(i, 0) + 1
		for i in range(n - 1, -1, -1):
			while len(s) != 0 and d[arr[i]] >= d[s[-1]]:
				s.pop()
			if len(s) != 0 and d[arr[i]] < d[s[-1]]:
				r.append(s[-1])
			else:
				r.append(-1)
			s.append(arr[i])
		return r[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		freq = {}
		for i in arr:
			if i in freq:
				freq[i] += 1
			else:
				freq[i] = 1
		ans = [-1] * n
		st = [0]
		for i in range(1, n):
			while st and freq[arr[i]] > freq[arr[st[-1]]]:
				t = st.pop()
				ans[t] = arr[i]
			st.append(i)
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			d[i] = d.get(i, 0) + 1
		p = []
		s = []
		for i in range(n - 1, -1, -1):
			if len(s) == 0:
				p.append(-1)
			else:
				flag = 0
				while len(s) != 0:
					if d[s[-1]] > d[arr[i]]:
						p.append(s[-1])
						flag = 1
						break
					else:
						s.pop()
				if flag == 0:
					p.append(-1)
			s.append(arr[i])
		p.reverse()
		return p


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		arr = arr[::-1]
		c = Counter(arr)
		dp = []
		ans = [-1] * n
		for i in range(0, n):
			while dp:
				if c[dp[-1]] > c[arr[i]]:
					ans[i] = dp[-1]
					break
				else:
					dp.pop()
			dp.append(arr[i])
		return ans[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		freq = {}
		for i in range(n):
			if arr[i] in freq:
				freq[arr[i]] += 1
			else:
				freq[arr[i]] = 1
		stack = []
		ngf = [-1 for _ in range(n)]
		for i in range(n):
			temp = freq[arr[i]]
			while len(stack):
				if temp > freq[arr[stack[-1]]]:
					ngf[stack[-1]] = arr[i]
					stack.pop()
				else:
					break
			stack.append(i)
		return ngf


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = dict()
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		res = []
		stk = []
		for i in arr[::-1]:
			if stk is None:
				res.append(-1)
				stk.append(i)
				continue
			while stk and d[stk[-1]] <= d[i]:
				stk.pop()
			if stk:
				res.append(stk[-1])
				stk.append(i)
			else:
				res.append(-1)
				stk.append(i)
		return res[::-1]


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		freq_dict = Counter(arr)
		stack = []
		ans = [0] * n
		for indx in range(n - 1, -1, -1):
			curfreq = freq_dict[arr[indx]]
			while stack and curfreq >= stack[-1][1]:
				stack.pop()
			if len(stack) == 0:
				ans[indx] = -1
			else:
				ans[indx] = stack[-1][0]
			stack.append((arr[indx], freq_dict[arr[indx]]))
		return ans


from collections import Counter

class Solution:

	def print_next_greater_freq(self, arr, n):
		result = []
		st = []
		count = Counter(arr)
		for i in range(n - 1, -1, -1):
			while st and count[st[-1]] <= count[arr[i]]:
				st.pop()
			if st:
				result.append(st[-1])
			else:
				result.append(-1)
			st.append(arr[i])
		return result[::-1]


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			try:
				d[i] += 1
			except:
				d[i] = 1
		stack = []
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				stack.append(arr[i])
				arr[i] = -1
			else:
				while len(stack) > 0 and d[stack[-1]] <= d[arr[i]]:
					stack.pop()
				if len(stack) == 0:
					stack.append(arr[i])
					arr[i] = -1
				else:
					temp = arr[i]
					arr[i] = stack[-1]
					stack.append(temp)
		return arr


class Solution:

	def print_next_greater_freq(self, arr, n):
		req = [-1] * n
		dic = {}
		for i in range(n):
			if arr[i] not in dic:
				dic[arr[i]] = 1
			else:
				dic[arr[i]] += 1
		stack = []
		j = n - 1
		while j in range(0, n):
			while stack:
				if dic[arr[j]] < dic[stack[-1]]:
					req[j] = stack[-1]
					break
				else:
					stack.pop()
			stack.append(arr[j])
			j -= 1
		return req


class Solution:

	def print_next_greater_freq(self, arr, n):
		ans = []
		dicts = {}
		stack = []
		for i in range(n):
			ans.append(-1)
		for j in range(n):
			if arr[j] in dicts:
				dicts[arr[j]] += 1
			else:
				dicts[arr[j]] = 1
		stack.append(arr[n - 1])
		k = n - 1
		while k in range(0, n):
			while stack:
				if dicts[arr[k]] < dicts[stack[-1]]:
					ans[k] = stack[-1]
					break
				stack.pop()
			stack.append(arr[k])
			k -= 1
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		s = dict()
		for i in range(n):
			try:
				s[arr[i]] += 1
			except:
				s[arr[i]] = 1
		r = []
		ans = []
		for j in range(n - 1, -1, -1):
			while r and s[arr[j]] >= s[r[-1]]:
				r.pop()
			if not r:
				ans.append(-1)
			else:
				ans.append(r[-1])
			r.append(arr[j])
		ans.reverse()
		return ans


from collections import defaultdict

class Solution:

	def print_next_greater_freq(self, arr, n):
		stack = []
		ans = []
		d = defaultdict(int)
		for i in arr:
			d[i] += 1
		for i in range(n - 1, -1, -1):
			if len(stack) == 0:
				ans.append(-1)
			else:
				while len(stack) > 0:
					if d[stack[-1]] <= d[arr[i]]:
						stack.pop()
					else:
						break
				if len(stack) == 0:
					ans.append(-1)
				else:
					ans.append(stack[-1])
			stack.append(arr[i])
		ans.reverse()
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		s = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		ans = [0] * n
		ans[n - 1] = -1
		s.append(arr[n - 1])
		for i in range(n - 2, -1, -1):
			ans[i] = -1
			while s:
				if d[s[-1]] > d[arr[i]]:
					ans[i] = s[-1]
					break
				s.pop()
			s.append(arr[i])
		return ans


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		res = [-1] * len(arr)
		freq = []
		ind = []
		val = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in arr:
			freq.append(d[i])
		j = n - 1
		for v in range(len(freq) - 1, -1, -1):
			if len(val) == 0:
				res[j] = -1
				j -= 1
			elif val[-1] > freq[v]:
				res[j] = arr[ind[-1]]
				j -= 1
			else:
				while val and val[-1] <= freq[v]:
					val.pop()
					ind.pop()
				if len(val) == 0:
					res[j] = -1
					j -= 1
				elif val[-1] > freq[v]:
					res[j] = arr[ind[-1]]
					j -= 1
			val.append(freq[v])
			ind.append(v)
		return res


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		res = [-1] * n
		s = [arr[-1]]
		for i in range(n - 2, -1, -1):
			if len(s) > 0 and d[arr[i]] < d[s[-1]]:
				res[i] = s[-1]
			else:
				l = len(s) - 1
				while l != -1:
					if d[arr[i]] < d[s[l]]:
						res[i] = s[l]
						break
					else:
						s.pop()
					l = l - 1
			s.append(arr[i])
		return res


class Solution:

	def print_next_greater_freq(self, arr, n):
		d = {}
		for i in arr:
			d[i] = 1 + d.get(i, 0)
		stack = [arr[-1]]
		res = [-1] * n
		for i in range(n):
			temp = d[arr[i]]
			while len(stack):
				if temp > d[arr[stack[-1]]]:
					res[stack[-1]] = arr[i]
					stack.pop()
				else:
					break
			stack.append(i)
		return res