狐狸喜欢排列!她提出了以下问题并请 Cat 解决:
给你一个偶数正整数 $$$n$$$ 和一个长度为 $$$n$$$ 的排列 $$$^\dagger$$$ $$$p$$$。
长度为 $$$n$$$ 的另一个排列 $$$q$$$ 的分数是长度为 $$$n$$$ 的数组 $$$a$$$ 中局部最大值的数量,其中对于所有 $$$i$$$ ($$$1 \le i \le n$$$),$$$a_i = p_i + q_i$$$ ($$$1 \le i \le n$$$)。换句话说,$$$q$$$ 的分数是 $$$i$$$ 的数量,使得 $$$1 < i < n$$$ (注意严格的不等式)、$$$a_{i-1} < a_i$$$ 和 $$$a_i > a_{i+1}$$$ (再次注意严格的不等式)。
找到给定 $$$n$$$ 和 $$$p$$$ 获得最高分数的排列 $$$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$$$ 在给定约束下最大化分数。
示例
输入 #1
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
输出 #1
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$$$ 局部最大值。