CF1973C Cat, Fox and Double Maximum

Fox 喜欢排列！她想出了如下问题并让 Cat 来解决： 给定一个偶数正整数 $n$ 和一个长度为 $n$ 的排列 $^\dagger$ $p$。 对于另一个长度为 $n$ 的排列 $q$，定义数组 $a$，其中 $a_i = p_i + q_i$（$1 \le i \le n$）。$q$ 的得分为 $a$ 中局部极大值的个数。也就是说，$q$ 的得分等于满足 $1 < i < n$（注意是严格不等式）、$a_{i-1} < a_i$ 且 $a_i > a_{i+1}$ 的 $i$ 的个数（同样注意是严格不等式）。 请你找到一个排列 $q$，使得得分最大。如果有多个这样的排列，输出任意一个即可。 $^\dagger$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 的 $n$ 个不同整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但出现了 $4$）。

输入的第一行为一个整数 $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$ 在给定约束下得分最大。如果有多个答案，输出任意一个即可。

在第一个样例中，$a = [3, 6, 4, 7]$。该数组只有一个局部极大值（在第二个位置），因此所选排列 $q$ 的得分为 $1$。可以证明在约束下这是最优得分。 在最后一个样例中，得到的数组 $a = [6, 6, 12, 7, 14, 7, 14, 6]$ 有 $3$ 个局部极大值，分别在第三、第五和第七个位置。 由 ChatGPT 4.1 翻译