Permutation Operations
Contest: Codeforces Global Round 23
Difficulty rating: 1300
Tags: constructive algorithms, greedy, implementation, math

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
4
4
1 2 3 4
5
1 3 2 4 5
3
2 3 1
1
1

Example output:
1 1 1 1
1 4 3 2 1
1 3 3
1

Editorial:
Step 1:
Task: Try to prove that the answer is always zero. Or in other words, we can always make the array $$$a$$$ non-decreasing.
Solution: We will prove this fact in next stpes.
Step 2:
Task: If some array $$$a$$$ is non-decreasing, what can we say about array $$$d=[a_{2}-a_{1}, a_{3}-a_{2}, /dots a_{n}-a_{n-1}]$$$?
Solution: It's obvious that all elements of array $$$d$$$ should be non-negative.
Step 3:
Task: If we perform the $$$i$$$-th operation on the suffix starting at index $$$j$$$, what happens to array $$$d$$$?
Solution: All elements of it will remain the same except $$$d_{j-1}=a_{j}-a_{j-1}$$$ which will increase by $$$i$$$.
Step 4:
Task: Considering the fact that array $$$a$$$ consists only of positive integers, what can we say about $$$d_{i}=a_{i+1}-a_{i}$$$?
Solution: Since $$$a_{i+1} \le 0$$$, we can say that $$$d_{i} \ge -a_{i}$$$.
Step 5:
Task: Using step 3 and 4 and knowing that $$$a$$$ is a permutation of numbers $$$1$$$ to $$$n$$$, what can we do to make all elements of $$$d$$$ non-negative?
Solution: for $$$i \le n-1$$$, we can perform $$$a_{i}$$$-th operation on the suffix starting from index $$$i+1$$$. So $$$d_{i}$$$ will increase by $$$a_{i}$$$ and since we knew that $$$d_{i} \ge -a_{i}$$$, after performing this operation $$$d_{i} \ge 0$$$ will hold. So after this steps, elements of $$$d$$$ will be non-negative and according to Step 2, that's exactly what we want. It's also easy to see that it doesn't matter how we perform $$$a_{n}$$$-th operation, so we can do anything we want.