Permutation Operations

题意翻译

你有一个长度为 $n$ 的排列，同时你可以进行 $n$ 次操作，在第 $i$ 次操作时你可以选择该排列的一个后缀，让它们加上 $i$ ，最终目的是让这个序列变成**严格单调递增**。 若第 $i$ 次操作改变的是该排列的 $x_i,x_i+1,\cdots,n$，输出 $x_1,x_2,\cdots,x_n$。

题目描述

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

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

4
4
1 2 3 4
5
1 3 2 4 5
3
2 3 1
1
1

输出样例 #1

1 1 1 1
1 4 3 2 1
1 3 3
1

说明

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.

**排列操作**

**题意翻译**
给定一个长度为 $ n $ 的排列，允许进行 $ n $ 次操作。在第 $ i $ 次操作时，你可以选择排列中的一个非空后缀，并使其所有元素增加 $ i $。操作的目的是使最终序列变成**严格单调递增**。如果第 $ i $ 次操作改变的是排列的 $ x_i, x_i+1, \cdots, n $，输出 $ x_1, x_2, \cdots, x_n $。

**题目描述**
给定一个大小为 $ 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 \cdot 10^5 $。

**输出格式**
对于每个测试用例，打印 $ n $ 个整数 $ x_1, x_2, \ldots, x_n $（对于每个 $ 1 \le i \le n $，都有 $ 1 \le x_i \le n $），表明第 $ i $ 个操作必须应用于从索引 $ x_i $ 开始的后缀。如果有多个答案，则输出其中任何一个。

**输入输出样例**

**输入样例 #1**
```
4
4
1 2 3 4
5
1 3 2 4 5
3
2 3 1
1
1
```

**输出样例 #1**
```
1 1 1 1
1 4 3 2 1
1 3 3
1
```**排列操作** **题意翻译** 给定一个长度为 $ n $ 的排列，允许进行 $ n $ 次操作。在第 $ i $ 次操作时，你可以选择排列中的一个非空后缀，并使其所有元素增加 $ i $。操作的目的是使最终序列变成**严格单调递增**。如果第 $ i $ 次操作改变的是排列的 $ x_i, x_i+1, \cdots, n $，输出 $ x_1, x_2, \cdots, x_n $。 **题目描述** 给定一个大小为 $ 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 \cdot 10^5 $。 **输出格式** 对于每个测试用例，打印 $ n $ 个整数 $ x_1, x_2, \ldots, x_n $（对于每个 $ 1 \le i \le n $，都有 $ 1 \le x_i \le n $），表明第 $ i $ 个操作必须应用于从索引 $ x_i $ 开始的后缀。如果有多个答案，则输出其中任何一个。 **输入输出样例** **输入样例 #1** ``` 4 4 1 2 3 4 5 1 3 2 4 5 3 2 3 1 1 1 ``` **输出样例 #1** ``` 1 1 1 1 1 4 3 2 1 1 3 3 1 ```