CF1746C Permutation Operations

给定一个长度为 $n$ 的排列 $a$，你需要对其进行 $n$ 次操作。在第 $i$ 次操作中，你可以选择 $a$ 的一个非空后缀，并将该后缀的所有元素都增加 $i$。你应该如何进行操作，使得最终数组中的逆序对数量最小？ 注意，你可以对同一个后缀进行任意多次操作。 一个长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中每个整数 $1$ 到 $n$ 恰好出现一次。后缀是指数组中包含最后一个元素的若干连续元素。数组 $a$ 中的逆序对是指一对下标 $(i, j)$，满足 $i > j$ 且 $a_i < a_j$。

每个测试点包含多组测试数据。第一行包含一个整数 $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 \times 10^5$。

对于每个测试用例，输出 $n$ 个整数 $x_1, x_2, \ldots, x_n$（$1 \le x_i \le n$，$1 \le i \le n$），表示第 $i$ 次操作应当选择从下标 $x_i$ 开始的后缀。如果有多种方案，输出任意一种即可。

在第一个测试用例中，一种最优方案是每次操作都选择整个数组（即选择从下标 $1$ 开始的后缀）。最终数组 $[11, 12, 13, 14]$ 中没有逆序对。 在第二个测试用例中，$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$ 中没有逆序对。 由 ChatGPT 4.1 翻译