311353: CF1973C. Cat, Fox and Double Maximum

C. Cat, Fox and Double Maximumtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

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

ExampleInput

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

Output

2 4 1 3
3 1 4 2
2 5 1 4 3 6
5 4 8 2 7 1 6 3

Note

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.

题目大意：
狐狸喜欢排列！她想出了这个问题并要求猫来解决：

给定一个偶数正整数 \( 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 个局部最大值——在第三个、第五个和第七个位置。