CF2001B.Generate Permutation

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

Misuki 有两台打字机，第一台从左到右写字，指针初始指向 $1$；第二台从右到左写字，指针初始指向 $n$。

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

• 写数字：将当前数组 $a$ 中未出现的最小正整数写入 $a_i$，其中 $i$ 是指针当前指向的位置。只有当 $a_i = -1$ 时才能进行此操作。
• 回车：将指针返回到初始位置（即第一台打字机返回到 $1$，第二台打字机返回到 $n$）。
• 移动指针：将指针移动到下一个位置。设指针当前指向 $i$，若使用第一台打字机，则 $i := i + 1$，否则 $i := i - 1$。只有当操作后 $1 \le i \le n$ 时才能进行此操作。

你的任务是构造一个长度为 $n$ 的排列 $p$，使得无论 Misuki 使用哪一台打字机，将 $a$ 变为 $p$ 所需的最小回车操作次数都相同。如果无法做到，输出 $-1$。

如果有多个满足条件的排列，可以输出任意一个。

每个测试点包含多组测试数据。输入的第一行为一个整数 $t$（$1 \le t \le 500$），表示测试数据组数。

每组测试数据的第一行为一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示排列的长度。

保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出一行 $n$ 个整数，表示长度为 $n$ 的排列 $p$，使得无论 Misuki 使用哪台打字机，将 $a$ 变为 $p$ 所需的最小回车次数都相同。如果不存在这样的排列，输出 $-1$。

如果有多个满足条件的排列，可以输出任意一个。

在第一个测试点，可以通过 $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]$。

可以证明，使用第一台打字机时最小回车次数为 $0$，使用第二台打字机时为 $1$，因此该排列不合法。

同理，$p = [2, 1]$ 也不合法，所以 $n = 2$ 时无解。

在第三个测试点，可以通过 $1$ 次回车操作将 $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]$。

由 ChatGPT 4.1 翻译