← 返回题目列表

Codeforces · 1741/B

B. 有趣的排列

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

如果 $$$n$$$ 数字序列包含从 $$$1$$$ 到 $$$n$$$ 的所有数字恰好一次,则该序列称为排列。例如,序列 $$$[3, 1, 4, 2]$$$、[$$$1$$$] 和 $$$[2,1]$$$ 是排列,但 $$$[1,2,1]$$$、$$$[0,1]$$$ 和 $$$[1,3,4]$$$ 不是排列。

对于给定的数字 $$$n$$$,您需要进行排列 $$$p$$$ 以便同时满足两个要求:

- 对于每个元素 $$$p_i$$$,其至少一个邻居的值与 $$$p_i$$$ 的值相差一。也就是说,对于每个元素 $$$p_i$$$ ($$$1 \le i \le n$$$),其至少一个相邻元素(位于 $$$p_i$$$ 的左侧或右侧)必须是 $$$p_i + 1$$$ 或 $$$p_i - 1$$$。
- 排列必须没有固定点。也就是说,对于每个 $$$i$$$ ($$$1 \le i \le n$$$),必须满足 $$$p_i \neq i$$$。

让我们把满足这些要求的排列称为有趣的。

例如,令 $$$n = 4$$$。那么 [$$$4, 3, 1, 2$$$] 是一个有趣的排列,因为:

- $$$p_1=4$$$ 的右侧是 $$$p_2=p_1-1=4-1=3$$$;
- $$$p_2=3$$$ 左边是 $$$p_1=p_2+1=3+1=4$$$;
- $$$p_3=1$$$ 的右侧是 $$$p_4=p_3+1=1+1=2$$$;
- $$$p_4=2$$$ 左边是 $$$p_3=p_4-1=2-1=1$$$。
- 对于所有 $$$i$$$ 是 $$$p_i \ne i$$$。

对于给定的正整数 $$$n$$$,输出长度为 $$$n$$$ 的任何滑稽排列,如果长度为 $$$n$$$ 的滑稽排列不存在,则输出 -1。

输入

输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例由 f 个单行组成,其中包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

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

输出

对于每个测试用例,在单独的行上打印:

- 长度为 $$$n$$$ 的任意有趣排列 $$$p$$$;
- 如果您要查找的排列不存在,则为数字 -1。

示例

输入 #1

5
4
3
7
5
2

输出 #1

3 4 2 1
-1
6 7 4 5 3 2 1
5 4 1 2 3
2 1

注意

第一个测试用例在问题陈述中进行了解释。

在第二个测试用例中,不可能进行所需的排列:排列 $$$[1, 2, 3]$$$、$$$[1, 3, 2]$$$、$$$[2, 1, 3]$$$、$$$[3, 2, 1]$$$ 具有固定点,并且在 $$$[2, 3, 1]$$$ 和$$$[3, 1, 2]$$$ 并非所有位置都满足第一个条件。