配点 : 100 点
問題文
(1,2,\dots,N) 的排列 判断是否存在满足以下条件的 P 。如果存在,请构建一个。
- 整数 1 \le i < j < k \le N 满足 P_i < P_j < P_k 和整数的事物的数量 满足 1 \le i < j < k \le N 满足 P_i > P_j > P_k 的项目数量相等。 您将获得
T 测试用例,因此请解决每个测试用例的问题。
制約
- 1 \le T \le 5 \times 10^5
- 3 \le N \le 5 \times 10^5
- 在测试用例中 N 的总和是 5 \times 10^5 下面。
- 所有输入均为整数。
入力
输入将以以下格式从标准输入提供。
T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T
在这里, 它代表第\text{test}_i 表示 i 个测试用例,并以以下格式给出。
N
出力
对于每个测试用例,如果没有满足条件的排列,
打印 -1 并开始一个新行。
如果存在,则满足条件的排列 输出 P ,用空格分隔并另起一行。 如果有多个解,可以输出其中任意一个。
入力例 1
2 3 4
出力例 1
1 3 2 2 4 1 3
对于第一个测试用例,排列 (1,3,2) 既不是单调递增也不是单调递减。因此,满足条件。
对于第二个测试用例,例如排列 考虑到 (2,4,1,3) ,(P_i,P_j,P_k) 可能的值对是:(2,4,1),(2,4,3),(4,1,3),(2,1,3) ,但所有这些三元组既不是单调递增也不是单调递减。因此,满足条件。