好的，下面是 B. 生成排列 的详细题解。

---

题目理解

有一个长度为 $n$ 的数组 $a$，初始全是 $-1$。
两台打字机：

• 第一台：指针初始在 $1$，只能向右移动，回车回到 $1$。
• 第二台：指针初始在 $n$，只能向左移动，回车回到 $n$。

写数字的规则固定：每次写当前不在 $a$ 中的最小正整数。
因此数字 $1, 2, \dots, n$ 会按这个顺序被写入数组。

我们需要构造一个排列 $p$，使得两台打字机写出 $p$ 所需的最少回车次数相等。

---

1. 最少回车次数的计算

设 $pos_x$ 表示数字 $x$ 在 $p$ 中的位置（$1 \le pos_x \le n$）。

第一台打字机（从左到右）

• 写 $x$ 时，指针必须在 $pos_x$。
• 写完 $x$ 后要写 $x+1$：
  • 若 $pos_{x+1} > pos_x$，指针可直接右移，不需要回车。
  • 若 $pos_{x+1} < pos_x$，指针无法左移，必须先回车到 $1$，再右移到 $pos_{x+1}$，需要 $1$ 次回车。

因此：

$$c_1 = \#\{x \in [1, n-1] \mid pos_x > pos_{x+1}\}$$

即位置序列 $pos_1, pos_2, \dots, pos_n$ 中下降的次数。

第二台打字机（从右到左）

• 写 $x$ 时，指针必须在 $pos_x$。
• 写完 $x$ 后要写 $x+1$：
  • 若 $pos_{x+1} < pos_x$，指针可直接左移，不需要回车。
  • 若 $pos_{x+1} > pos_x$，指针无法右移，必须先回车到 $n$，再左移到 $pos_{x+1}$，需要 $1$ 次回车。

因此：

$$c_2 = \#\{x \in [1, n-1] \mid pos_x < pos_{x+1}\}$$

即位置序列中上升的次数。

---

2. 关键等式

对于每一对相邻值 $(x, x+1)$，由于 $pos_x \neq pos_{x+1}$，要么 $pos_x < pos_{x+1}$，要么 $pos_x > pos_{x+1}$。
所以：

$$c_1 + c_2 = n - 1$$

这是一个常数。

要求 $c_1 = c_2$，代入得：

$$c_1 = c_2 = \frac{n-1}{2}$$

---

3. 解的可行性

• 当 $n$ 为偶数时，$\frac{n-1}{2}$ 不是整数，不可能有 $c_1 = c_2$。
  因此输出 $-1$。

• 当 $n$ 为奇数时，有解，且我们需要构造一个排列，使得位置序列中恰好有 $\frac{n-1}{2}$ 次上升和 $\frac{n-1}{2}$ 次下降。

---

4. 构造方法

标程给出的构造（以 $n=5$ 为例）：

$$p = [4,5,2,3,1]$$

一般形式：

$$p = [n-1,\ n,\ n-3,\ n-2,\ n-5,\ n-4,\ \dots,\ 4,5,2,3,1] $$

验证 $n=5$ 的情况

• $p = [4,5,2,3,1]$
• 位置：$pos_1=5,\ pos_2=3,\ pos_3=4,\ pos_4=1,\ pos_5=2$
• 位置序列：$[5,3,4,1,2]$
• 比较：
  • $5 > 3$（下降）
  • $3 < 4$（上升）
  • $4 > 1$（下降）
  • $1 < 2$（上升）
• 上升次数 $=2$，下降次数 $=2$，$n-1=4$，满足条件。

为什么这个构造有效？

• 它把较大的数交替放在两端，较小的数放在中间。
• 位置序列会自然产生交替的上升和下降，且上升和下降次数相等。
• 最后一个元素是 $1$，保证最后一步是上升或下降的边界处理正确。

---

5. 算法步骤

对于每个测试用例：

1. 如果 $n$ 是偶数，输出 $-1$。
2. 如果 $n$ 是奇数，按上述模式构造排列并输出。

---

6. 时间复杂度

每个测试用例 $O(n)$ 构造，$O(n)$ 输出。
总 $n$ 之和不超过 $2\times 10^5$，因此总复杂度 $O(\sum n)$。

---

7. 总结

• 核心转化：回车次数 $c_1$ 和 $c_2$ 分别等于位置序列的下降次数和上升次数。
• 由 $c_1 + c_2 = n-1$ 得 $c_1 = c_2$ 当且仅当 $n$ 为奇数。
• 构造方法简单，直接按模式填充即可。