There are N people waiting in a queue at ATM. The i^{th} person in the queue has a power level equal to A_{i} (1 ≤ A_{i} ≤ N). The following process happens every second till the queue is not empty.

The person in front of the queue uses the ATM and then leaves the queue.
After the first step, if the queue is empty, the process stops. Otherwise, for each person from left to right (except for the first person in the queue), if the person has a \textbf{strictly greater} power level than the person in front of him, he will overtake the person in front, i.e. their positions get swapped. Note that the overtaking happens one after the other from left to right, i.e. state of the queue changes after every overtake.

For each person, find the time at which they will use the ATM.

\textbf{Note}: Please refer to the explanation section for a simulation of one such scenario.

------ Input Format ------ 

- First line of input contains T, the number of test cases. Then T test cases follow.
- Each test case consists of two lines of input.
- First line of each test case contains N, the number of people in the queue.
- Second line of each test case contains N positive integers A_{i}, the power level of i^{th} person.

------ Output Format ------ 

For each test case, print a line containing N numbers where i^{th} number is equal to the time at which i^{th} person uses the ATM.

------ Constraints ------ 

$1 ≤ T ≤ 2 \cdot 10^{4}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ N$
- Sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
5
2 3 4 1 5
4
1 2 4 2
10
5 1 3 7 6 9 8 9 2 10
----- Sample Output 1 ------ 
1 4 2 5 3
1 3 2 4
1 10 2 3 8 4 7 5 9 6
----- explanation 1 ------ 
Test Case $1$:
Initially, let the order of people in the queue is $[1, 2, 3, 4, 5]$, and their power levels are $2, 3, 4, 1$ and  $5$ respectively.
- During the $1^{st}$ second, $1$ uses the ATM and leaves. The order of the people in the queue will be $[2, 3, 4, 5]$ after $1$ leaves. Now people start overtaking ($2^{nd}$ step of the process). Since $3$ is the $2^{nd}$ person in the queue and $2$ is in front of him and $A_{2}$  $A_{4}$, so there will be no overtaking here. Finally, $5$ is the $4^{th}$ person and $4$ is in front of him. And since $A_{4}$ < $A_{5}$, $5$ will overtake $4$ and The order of the people in the queue will be $[3, 2, 5, 4]$ after the $1$st second.

- During the $2^{nd}$ second, $3$ is in front of the queue. He will use the ATM and leave. The order of the people in the queue will become $[2, 5, 4]$. Since $5$ is the $2^{nd}$ person in the queue with $2$ in front of him and $A_{2}$  $A_{4}$, so $4$ can't overtake $2$. By the end of $2^{nd}$ second, the order of people in the queue is $[5, 2, 4$].

- During the $3^{rd}$ second, $5$ is in front of the queue. He will use the ATM and leave. After this, the queue will be $2, 4$. And since $A_{2}$ > $A_{4}$, there will be no overtaking.

- During the $4^{th}$ second, $2$ uses the ATM and leaves. 

- During the $5^{th}$ second, $4$ uses the ATM and leaves.

Hence, $1, 2, 3, 4$ and $5$ use the ATM at $1, 4, 2, 5, 3$ second, respectively.

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Constructive algorithms


Solutions:
import heapq as hq
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [1] * n
	start = 0
	time = 1
	first = [(-a[start], start)]
	hq.heapify(first)
	while len(first):
		x = hq.heappop(first)
		ans[x[1]] = time
		time += 1
		start += 1
		if start < n:
			hq.heappush(first, (-a[start], start))
			start += 1
		if start < n:
			hq.heappush(first, (-a[start], start))
	print(*ans)


import heapq as hq
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = [0] * n
	ans[0] = 1
	rank = 2
	p = 1
	temp = []
	hq.heapify(temp)
	while True:
		while p < n and p <= 2 * rank - 2:
			hq.heappush(temp, [-1 * l[p], p])
			p = p + 1
		ans[hq.heappop(temp)[1]] = rank
		rank = rank + 1
		if p > n - 1:
			break
	while len(temp) != 0:
		ans[hq.heappop(temp)[1]] = rank
		rank = rank + 1
	for i in ans:
		print(i, end=' ')
	print()


import heapq
testcases = int(input())
while testcases:
	N = int(input())
	person_pow = list(map(int, input().split()))
	time = [1] * N
	curr_time = 1
	st = 0
	front_person = [(-person_pow[st], st)]
	heapq.heapify(front_person)
	while len(front_person):
		person = heapq.heappop(front_person)
		time[person[1]] = curr_time
		curr_time += 1
		st += 1
		if st < N:
			heapq.heappush(front_person, (-person_pow[st], st))
			st += 1
		if st < N:
			heapq.heappush(front_person, (-person_pow[st], st))
	print(*time)
	testcases -= 1


from heapq import *
for _ in range(int(input())):
	n = int(input())
	power = list(map(int, input().split()))
	l = [(-1 * power[0], 0)]
	heapify(l)
	ans = [0 for i in range(n)]
	i = 1
	time = 1
	while len(l):
		x = heappop(l)
		if i < n:
			heappush(l, (-1 * power[i], i))
			i += 1
		if i < n:
			heappush(l, (-1 * power[i], i))
			i += 1
		ans[x[1]] = time
		time += 1
	print(' '.join([str(ans[i]) for i in range(n)]))


from collections import defaultdict
import heapq
for _ in range(int(input())):
	n = int(input())
	power = list(map(int, input().split()))
	maxHeap = []
	ansTable = {0: 1}
	second = 2
	idx = 1
	while idx != n:
		heapq.heappush(maxHeap, [-power[idx], idx])
		if idx + 1 != n:
			idx += 1
			heapq.heappush(maxHeap, [-power[idx], idx])
		(p, i) = heapq.heappop(maxHeap)
		ansTable[i] = second
		second += 1
		idx += 1
	while maxHeap:
		(p, i) = heapq.heappop(maxHeap)
		ansTable[i] = second
		second += 1
	for i in range(n):
		print(ansTable[i], end=' ')
	print()


from heapq import heappop, heappush, merge, heapify
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	power = list(map(int, input().split()))
	time = 1
	ans = [0] * n
	heaps = []
	heappush(heaps, (-power[0], 0))
	idx = 1
	while heaps:
		(pw, ind) = heappop(heaps)
		ans[ind] = time
		if idx < n:
			heappush(heaps, (-power[idx], idx))
			idx += 1
		if idx < n:
			heappush(heaps, (-power[idx], idx))
			idx += 1
		time += 1
	sys.stdout.write(' '.join((str(x) for x in ans)))
	sys.stdout.write('\n')