← 返回题目列表

Codeforces · 2001/B

B. 生成排列

中文机器翻译题面 查看原题

有一个长度为$$$n$$$的整数序列$$$a$$$,其中每个元素最初为$$$-1$$$。

美月有两台打字机,第一台打字机从左到右书写字母,指针最初指向 $$$1$$$,另一台打字机从右到左书写字母,指针最初指向 $$$n$$$。

Misuki会选择一台打字机并用它执行以下操作,直到$$$a$$$成为$$$[1, 2, \ldots, n]$$$的排列

- 写入数字:将数组$$$a$$$中不存在的最小正整数写入元素$$$a_i$$$,$$$i$$$是指针指向的位置。只有当$$$a_i = -1$$$时才能进行这样的操作。
- 回车:将指针返回到其初始位置(即第一台打字机为 $$$1$$$,第二台打字机为 $$$n$$$)
- 移动指针:将指针移动到下一个位置,令 $$$i$$$ 为指针在此操作之前所指向的位置,如果 Misuki 使用第一台打字机,则会发生 $$$i := i + 1$$$,否则会发生 $$$i := i - 1$$$。仅当运算后 $$$1 \le i \le n$$$ 成立时,才能进行此类运算。

你的任务是构造长度为 $$$n$$$ 的任意排列 $$$p$$$,使得无论 Misuki 使用哪台打字机,$$$a = p$$$ 所需的最少回车操作次数都是相同的。

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 排列的长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行 $$$n$$$ 整数,表示长度 $$$n$$$ 的排列 $$$p$$$,使得无论 Misuki 使用哪台打字机,使 $$$a = p$$$ 所需的最少回车操作次数都是相同的,如果不可能的话,则输出 $$$-1$$$。

如果有多个有效排列,则可以输出其中任何一个。

示例

输入 #1

3
1
2
3

输出 #1

1
-1
3 1 2

注意

在第一个测试用例中,可以使用 $$$0$$$ 回车操作使 $$$a = p = [1]$$$ 。

在第二个测试用例中,可以使用最少数量的回车符来使 $$$a = p = [1, 2]$$$ 如下:

如果 Misuki 使用第一台打字机:

- 写入数字:将 $$$1$$$ 写入 $$$a_1$$$,$$$a$$$ 变为 $$$[1, -1]$$$
- 移动指针:将指针移动到下一个位置。 (即$$$2$$$)
- 写入数字:将 $$$2$$$ 写入 $$$a_2$$$,$$$a$$$ 变为 $$$[1, 2]$$$

如果 Misuki 使用第二台打字机:

- 移动指针:将指针移动到下一个位置。 (即$$$1$$$)
- 写入数字:将 $$$1$$$ 写入 $$$a_1$$$,$$$a$$$ 变为 $$$[1, -1]$$$
- 回车:返回指向$$$2$$$的指针。
- 写入数字:将 $$$2$$$ 写入 $$$a_2$$$,$$$a$$$ 变为 $$$[1, 2]$$$

可以证明,使用第一个打字机时将 $$$a$$$ 转换为 $$$p$$$ 所需的最少回车次数为 $$$0$$$,使用第二个打字机时为 $$$1$$$,因此这种排列无效。

同样,$$$p = [2, 1]$$$ 也是无效的,因此 $$$n = 2$$$ 没有解。

在第三个测试用例中,可以使用第一台和第二台打字机制作 $$$a = p = [3, 1, 2]$$$ 并使用 $$$1$$$ 回车符。可以证明,对于两台打字机来说,都不可能用$$$0$$$回车来写出$$$p$$$。

使用第一台打字机可以:

- 移动指针:将指针移动到下一个位置。 (即$$$2$$$)
- 写入数字:将$$$1$$$写入$$$a_2$$$,$$$a$$$变为$$$[-1, 1, -1]$$$
- 移动指针:将指针移动到下一个位置。 (即$$$3$$$)
- 写入数字:将$$$2$$$写入$$$a_3$$$,$$$a$$$变为$$$[-1, 1, 2]$$$
- 回车:返回指向$$$1$$$的指针。
- 写入数字:将$$$3$$$写入$$$a_1$$$,$$$a$$$ 变为$$$[3,1,2]$$$

使用第二台打字机可以:

- 移动指针:将指针移动到下一个位置。 (即$$$2$$$)
- 写入数字:将$$$1$$$写入$$$a_2$$$,$$$a$$$变为$$$[-1, 1, -1]$$$
- 回车:返回指向$$$3$$$的指针。
- 写入数字:将$$$2$$$写入$$$a_3$$$,$$$a$$$变为$$$[-1, 1, 2]$$$
- 移动指针:将指针移动到下一个位置。 (即$$$2$$$)
- 移动指针:将指针移动到下一个位置。 (即$$$1$$$)
- 写入数字:将 $$$3$$$ 写入 $$$a_1$$$,$$$a$$$ 变为 $$$[3, 1, 2]$$$