You are given a permutation $a$ of size $n$ and you should perform $n$ operations on it. In the $i$-th operation, you can choose a non-empty suffix of $a$ and increase all of its elements by $i$. How can we perform the operations to minimize the number of inversions in the final array?

Note that you can perform operations on the same suffix any number of times you want.

A permutation of size $n$ is an array of size $n$ such that each integer from $1$ to $n$ occurs exactly once in this array. A suffix is several consecutive elements of an array that include the last element of the array. An inversion in an array $a$ is a pair of indices $(i, j)$ such that $i > j$ and $a_{i} < a_{j}$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the size of the array.

The second line contains $n$ distinct integers $a_{1}, a_{2}, \dots, a_{n}$ ($1 \le a_i \le n$), the initial permutation $a$.

It's guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print $n$ integers $x_{1}, x_{2}, \ldots, x_{n}$ ($1 \le x_{i} \le n$ for each $1 \le i \le n$) indicating that the $i$-th operation must be applied to the suffix starting at index $x_{i}$. If there are multiple answers, print any of them.


-----Examples-----

Input
4
4
1 2 3 4
5
1 3 2 4 5
3
2 3 1
1
1
Output
1 1 1 1
1 4 3 2 1
1 3 3
1


-----Note-----

In the first test case one of the optimal solutions is to increase the whole array on each operation (that is, choose the suffix starting at index $1$). The final array $[11, 12, 13, 14]$ contains $0$ inversions.

In the second test case, $a$ will be equal to $[2, 4, 3, 5, 6]$, $[2, 4, 3, 7, 8]$, $[2, 4, 6, 10, 11]$, $[2, 8, 10, 14, 15]$ and $[7, 13, 15, 19, 20]$ after the first, second, third, fourth, and fifth operations, respectively. So the final array $a$ has zero inversions.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms

Implementation

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline
print = sys.stdout.write
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	inx = [0] * (n + 1)
	for i in range(n):
		inx[a[i]] = i + 1
	print(' '.join((str(inx[n - i]) for i in range(n))))
	print('\n')


for _ in range(int(input())):
	n = int(input())
	score = list(map(int, input().split(' ')))
	mass = [0] * n
	for i in range(n):
		mass[score[i] - 1] = i + 2
	for i in range(n):
		if mass[i] > n:
			mass[i] = 1
	print(' '.join(map(str, mass)))


print = __import__('sys').stdout.write
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	inx = [0] * (n + 1)
	for i in range(n):
		inx[a[i]] = i + 1
	print(' '.join((str(inx[n - i]) for i in range(n))))
	print('\n')


M = int(input())
result = []
for x in range(M):
	n = int(input())
	numbers = input().split(' ')
	arr = []
	for num in numbers:
		arr.append(int(num))
	d = dict()
	for i in range(n):
		d[arr[i]] = i
	aux = []
	for i in range(n):
		aux.append(d[n - i] + 1)
	result.append(aux)
for r in result:
	st = [str(e) for e in r]
	print(' '.join(st))


def argsort(seq):
	return sorted(range(len(seq)), key=seq.__getitem__)
fl = 'input.txt'
import sys
import math
flh = sys.stdin
test_cases = int(flh.readline())
res = []
for case in range(test_cases):
	n = int(flh.readline())
	a = [int(x) for x in flh.readline().strip().split()]
	d = [0]
	for i in range(1, len(a)):
		d.append(max(0, a[i - 1] - a[i]))
	res = argsort(d)
	print(' '.join(map(str, [r + 1 for r in res])))


for s in [*open(0)][2::2]:
	s = list(map(int, s.split()))
	a = [1] * len(s)
	for i in range(len(s) - 1):
		a[s[i] - 1] = i + 2
	print(*a)


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	x = int(input())
	n = x
	l = [0] * x
	s = list(map(int, input().split()))
	m = s[0]
	for i in range(x):
		l[n - s[i]] = i + 1
	print(*l)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	loc = [0 for i in range(n)]
	for i in range(0, n):
		a[i] -= 1
		loc[a[i]] = i
	ans = ''
	for i in range(n):
		if loc[i] == n - 1:
			ans += '1' + ' '
		else:
			ans += str(loc[i] + 2) + ' '
	print(ans[:-1])


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	l = [0] * n
	for i in range(n):
		l[n - a[i]] = i + 1
	print(*l)
for i in range(int(input())):
	solve()


def permutation_operation(n, l):
	res = [1] * n
	for i in range(0, n - 1):
		res[l[i] - 1] = i + 2
	return res
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	res = permutation_operation(n, l)
	print(*res)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	res = [0] * n
	for i in range(n):
		res[n - lst[i]] = i + 1
	print(*res)


tc = int(input())
for i in range(0, tc):
	l = int(input())
	sequence = [int(part) for part in input().split()]
	op_arr = [1] * len(sequence)
	for z in range(0, len(sequence) - 1):
		op_arr[sequence[z] - 1] = z + 2
	print(*op_arr)


import math
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans = [1] * n
	for i in range(n):
		ans[n - arr[i]] = i + 1
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * n
	for i in range(n):
		b[n - a[i]] = i + 1
	print(*b)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		ans[n - arr[i]] = i + 1
	print(*ans)


from bisect import bisect_right
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = [0] * n
	for i in range(n):
		ans[n - l[i]] = i + 1
	print(*ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	li = [0] * n
	for j in range(n):
		li[n - a[j]] = j + 1
	print(*li)


def most_frequent(List):
	counter = 0
	num = List[0]
	for i in List:
		curr_frequency = List.count(i)
		if curr_frequency > counter:
			counter = curr_frequency
			num = i
	return num

def solve(n, arr):
	ans = [0 for i in range(n)]
	for i in range(n):
		ans[arr[i] - 1] = i + 1
	print(*reversed(ans))
for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	solve(n, arr)


t = int(input())

def solve():
	n = int(input())
	nums = [int(x) for x in input().split()]
	a = [(n - x, i) for (i, x) in enumerate(nums, 1)]
	a.sort()
	a = [x[1] for x in a]
	print(' '.join(map(str, a)))
for _ in range(t):
	solve()


for j in range(int(input())):
	leng = int(input())
	s = list(map(int, input().split()))
	a = [1] * leng
	for i in range(leng - 1):
		a[s[i] - 1] = i + 2
	print(*a)


def exe():
	d = {}
	for i in range(1, n + 1):
		d[i] = 0
	for i in range(n):
		d[lst[i]] = i + 1
	return [d[i] for i in range(n, 0, -1)]
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(*exe())


def permutation_operation(n, a):
	ans = [0] * n
	mp = {}
	for i in range(n):
		mp[n + 1 - a[i]] = i
	for i in range(n):
		ans[i] = mp[i + 1] + 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	result = permutation_operation(n, a)
	print(*result)


import math
t = int(input())
m = 1000000000.0 + 7

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	idx = [0] * (n + 1)
	for i in range(0, n):
		idx[arr[i]] = i
	for i in range(1, n + 1):
		if idx[i] == n - 1:
			print(1, end=' ')
		else:
			print(idx[i] + 2, end=' ')
	print()
for _ in range(t):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ops = [0] * n
	for i in range(n):
		ops[n - arr[i]] = i + 1
	for i in ops:
		print(i, end=' ')
	print('')


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[arr[i]] = i
	for j in range(n):
		print(d[n - j] + 1, end=' ')
	print()


TT = int(input())
while TT:
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = sorted(range(n), key=lambda k: a[k], reverse=True)
	for i in b:
		print(i + 1, end=' ')
	print()
	TT -= 1


pos = [None] * 100001
t = int(input())
for _ in range(t):
	n = int(input())
	ar = [int(item) for item in input().split()]
	for i in range(n):
		pos[ar[i]] = i + 1
	ans = []
	for i in range(n):
		ans.append(pos[n - i])
	print(*ans, sep=' ')


t = int(input())
for test_case in range(t):
	n = int(input())
	int_list = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		d[int_list[i]] = i + 1
	for i in range(n, 0, -1):
		print(d[i], end=' ')
	print()


import collections
import functools

def solve(A):
	n = len(A)
	res = [()] * n
	output = ['1'] * n
	for i in range(1, n):
		res[i] = (A[i] - A[i - 1], i)
	res.sort()
	for i in range(1, n):
		output[n - i] = str(res[i][1] + 1)
	return ' '.join(output)

def main():
	for _ in range(int(input())):
		input()
		A = [int(e) for e in input().split()]
		print(solve(A))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = {}
	for i in range(n):
		m[l[i]] = i
	ans = []
	for i in range(1, n + 1):
		ind = m[i]
		if ind == n - 1:
			ans.append(1)
		else:
			ans.append(ind + 2)
	print(*ans)


n = int(input())
for _ in range(n):
	a = int(input())
	b = list(map(int, input().split()))
	c = {}
	for i in range(1, 1 + a):
		c[a + 1 - b[i - 1]] = i
	for i in range(1, 1 + a):
		print(c[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		d[l[i]] = i
	for j in range(n):
		print(d[n - j] + 1, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	l1 = []
	for i in range(n):
		l1.append(-1)
	for i in range(n - 1):
		a = lst[i]
		l1[a - 1] = i + 2
	for i in l1:
		if i == -1:
			print(1, end=' ')
		else:
			print(i, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = a[0]
	b = [None] * n
	v = 0
	for j in a:
		b[v] = (p - j, v)
		p = j
		v += 1
	b.sort()
	s = ''
	for x in b:
		s += str(x[1] + 1)
		s += ' '
	print(s)


for _ in range(int(input())):
	a = int(input())
	b = [int(i) for i in input().split()]
	c = {}
	for i in range(len(b)):
		c[b[i]] = i
	output = []
	for i in range(a):
		print(c[a - i] + 1, end=' ')
	print()


def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
a = inp()
for i in range(a):
	c1 = 0
	c0 = 0
	_ = inlt()
	k = inlt()
	f = False
	maxc = k[0]
	l = []
	for x in k:
		maxc = max(x, maxc)
		l.append(maxc - x)
	l = sorted(range(len(l)), key=lambda k: l[k])
	l = [x + 1 for x in l]
	print(*l)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = [(a[i] - a[i + 1], i + 2) for i in range(n - 1)]
	d.sort()
	print(1, *[x[1] for x in d])


def main():
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		res = []
		for i in range(n - 1):
			res.append([a[i] - a[i + 1], i])
		res.sort()
		print(1, end=' ')
		for i in res:
			print(i[1] + 2, end=' ')
		print()
main()


def solve(t, n):
	pos = []
	for i in range(t):
		pos.append([n[i], i])
	pos.sort(reverse=True)
	num = []
	for i in pos:
		num.append(i[1] + 1)
	return num
for _ in range(int(input())):
	t = int(input())
	n = list(map(int, input().split()))
	print(*solve(t, n))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	lst = []
	lst2 = []
	for i in range(n):
		lst.append(n + 1 - a[i])
		lst2.append(i + 1)
	z = sorted(list(zip(lst, lst2)))
	res = []
	for (i, j) in z:
		res.append(j)
	print(*res)