CF1746C.Permutation Operations

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 \gt j$ and $a_{i} \lt a_{j}$.

给你一个长度为 $n$ 的排列 $a$，你需要对其执行 $n$ 次操作。在第 $i$ 次操作中，你可以选择 $a$ 的一个非空后缀，并将该后缀中所有元素增加 $i$。如何执行这些操作，使得最终数组中的逆序对数量最少？

注意：你可以任意多次对同一后缀执行操作。

长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中恰好包含从 $1$ 到 $n$ 的每个整数各一次。后缀是指包含数组最后一个元素的若干连续元素组成的子数组。数组 $a$ 中的一个逆序对是指一对下标 $(i, j)$，满足 $i \gt j$ 且 $a_{i} \lt a_{j}$。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 数组的大小。

第二行包含 $n$ 个互不相同的整数 $a_{1}, a_{2}, \dots, a_{n}$（$1 \le a_i \le n$），即初始排列 $a$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

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.

对于每个测试用例，输出 $n$ 个整数 $x_{1}, x_{2}, \ldots, x_{n}$（对每个 $1 \le i \le n$，满足 $1 \le x_{i} \le n$），表示第 $i$ 个操作必须应用于从索引 $x_{i}$ 开始的后缀。若存在多个答案，输出任意一个即可。

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.

在第一个测试用例中，一种最优解是在每次操作中对整个数组进行增加（即选择从下标 $1$ 开始的后缀）。最终数组 $[11, 12, 13, 14]$ 包含 $0$ 个逆序对。

在第二个测试用例中，经过第一次、第二次、第三次、第四次和第五次操作后，数组 $a$ 将分别变为 $[2, 4, 3, 5, 6]$、$[2, 4, 3, 7, 8]$、$[2, 4, 6, 10, 11]$、$[2, 8, 10, 14, 15]$ 和 $[7, 13, 15, 19, 20]$。因此，最终数组 $a$ 的逆序对数量为 $0$。