311353: CF1973C. Cat, Fox and Double Maximum
Description
Fox loves permutations! She came up with the following problem and asked Cat to solve it:
You are given an even positive integer $n$ and a permutation$^\dagger$ $p$ of length $n$.
The score of another permutation $q$ of length $n$ is the number of local maximums in the array $a$ of length $n$, where $a_i = p_i + q_i$ for all $i$ ($1 \le i \le n$). In other words, the score of $q$ is the number of $i$ such that $1 < i < n$ (note the strict inequalities), $a_{i-1} < a_i$, and $a_i > a_{i+1}$ (once again, note the strict inequalities).
Find the permutation $q$ that achieves the maximum score for given $n$ and $p$. If there exist multiple such permutations, you can pick any of them.
$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
InputThe first line of input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases in the input you will have to solve.
The first line of each test case contains one even integer $n$ ($4 \leq n \leq 10^5$, $n$ is even) — the length of the permutation $p$.
The second line of each test case contains the $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$). It is guaranteed that $p$ is a permutation of length $n$.
It is guaranteed that the sum of $n$ across all test cases doesn't exceed $10^5$.
OutputFor each test case, output one line containing any permutation of length $n$ (the array $q$), such that $q$ maximizes the score under the given constraints.
ExampleInput4 4 1 2 3 4 4 4 3 1 2 6 6 5 1 4 2 3 8 1 2 4 5 7 6 8 3Output
2 4 1 3 3 1 4 2 2 5 1 4 3 6 5 4 8 2 7 1 6 3Note
In the first example, $a = [3, 6, 4, 7]$. The array has just one local maximum (on the second position), so the score of the chosen permutation $q$ is $1$. It can be proven that this score is optimal under the constraints.
In the last example, the resulting array $a = [6, 6, 12, 7, 14, 7, 14, 6]$ has $3$ local maximums — on the third, fifth and seventh positions.
Output
狐狸喜欢排列！她想出了这个问题并要求猫来解决：
给定一个偶数正整数 \( n \) 和一个长度为 \( n \) 的排列 \( p \)。另一个长度为 \( n \) 的排列 \( q \) 的得分是在数组 \( a \) 中的局部最大值的数量，其中 \( a_i = p_i + q_i \) 对于所有 \( i \)（\( 1 \le i \le n \)）。换句话说，\( q \) 的得分是满足 \( 1 < i < n \)（注意严格不等式），\( a_{i-1} < a_i \)，且 \( a_i > a_{i+1} \) 的 \( i \) 的数量（再次注意严格不等式）。
找到给定 \( n \) 和 \( p \) 的排列 \( q \)，使得得分最大。如果存在多个这样的排列，你可以选择其中任何一个。
输入输出数据格式：
输入：
- 第一行包含一个整数 \( t \)（\( 1 \leq t \leq 10^4 \)）—— 输入中要解决的测试用例数量。
- 每个测试用例的第一行包含一个偶数整数 \( n \)（\( 4 \leq n \leq 10^5 \)，\( n \) 是偶数）—— 排列 \( p \) 的长度。
- 每个测试用例的第二行包含 \( n \) 个整数 \( p_1, p_2, \ldots, p_n \)（\( 1 \leq p_i \leq n \)）。保证 \( p \) 是长度为 \( n \) 的排列。
- 保证所有测试用例的 \( n \) 之和不超过 \( 10^5 \)。
输出：
- 对于每个测试用例，输出一行，包含一个长度为 \( n \) 的排列 \( q \)，使得 \( q \) 在给定约束下最大化得分。
示例输入输出：
输入：
```
4
4
1 2 3 4
4
4 3 1 2
6
6 5 1 4 2 3
8
1 2 4 5 7 6 8 3
```
输出：
```
2 4 1 3
3 1 4 2
2 5 1 4 3 6
5 4 8 2 7 1 6 3
```
注意：
在第一个例子中，\( a = [3, 6, 4, 7] \)。该数组只有一个局部最大值（在第二个位置），所以选择的排列 \( q \) 的得分是 1。可以证明，在约束条件下这个得分是最优的。
在最后一个例子中，得到的数组 \( a = [6, 6, 12, 7, 14, 7, 14, 6] \) 有 3 个局部最大值——在第三个、第五个和第七个位置。题目大意： 狐狸喜欢排列！她想出了这个问题并要求猫来解决： 给定一个偶数正整数 \( n \) 和一个长度为 \( n \) 的排列 \( p \)。另一个长度为 \( n \) 的排列 \( q \) 的得分是在数组 \( a \) 中的局部最大值的数量，其中 \( a_i = p_i + q_i \) 对于所有 \( i \)（\( 1 \le i \le n \)）。换句话说，\( q \) 的得分是满足 \( 1 < i < n \)（注意严格不等式），\( a_{i-1} < a_i \)，且 \( a_i > a_{i+1} \) 的 \( i \) 的数量（再次注意严格不等式）。 找到给定 \( n \) 和 \( p \) 的排列 \( q \)，使得得分最大。如果存在多个这样的排列，你可以选择其中任何一个。 输入输出数据格式： 输入： - 第一行包含一个整数 \( t \)（\( 1 \leq t \leq 10^4 \)）—— 输入中要解决的测试用例数量。 - 每个测试用例的第一行包含一个偶数整数 \( n \)（\( 4 \leq n \leq 10^5 \)，\( n \) 是偶数）—— 排列 \( p \) 的长度。 - 每个测试用例的第二行包含 \( n \) 个整数 \( p_1, p_2, \ldots, p_n \)（\( 1 \leq p_i \leq n \)）。保证 \( p \) 是长度为 \( n \) 的排列。 - 保证所有测试用例的 \( n \) 之和不超过 \( 10^5 \)。 输出： - 对于每个测试用例，输出一行，包含一个长度为 \( n \) 的排列 \( q \)，使得 \( q \) 在给定约束下最大化得分。 示例输入输出： 输入： ``` 4 4 1 2 3 4 4 4 3 1 2 6 6 5 1 4 2 3 8 1 2 4 5 7 6 8 3 ``` 输出： ``` 2 4 1 3 3 1 4 2 2 5 1 4 3 6 5 4 8 2 7 1 6 3 ``` 注意： 在第一个例子中，\( a = [3, 6, 4, 7] \)。该数组只有一个局部最大值（在第二个位置），所以选择的排列 \( q \) 的得分是 1。可以证明，在约束条件下这个得分是最优的。 在最后一个例子中，得到的数组 \( a = [6, 6, 12, 7, 14, 7, 14, 6] \) 有 3 个局部最大值——在第三个、第五个和第七个位置。