题目分析

我们需要构造一个长度为 $n$ 的整数数组 $a$，满足：

1. 相邻元素异号：$a_i \cdot a_{i+1} < 0$（正负交替）
2. 所有长度 ≥ 2 的子数组和为正
3. 字典序最小：在所有满足条件的数组中，$[|a_1|, |a_2|, \dots, |a_n|]$ 的字典序最小

---

第一步：符号确定

由条件 1，数组必须正负交替。我们可以假设 $a_1 < 0$（若 $a_1 > 0$ 则整体取反后绝对值序列不变，但符号模式可能影响子数组和，实际上最小化绝对值序列时 $a_1$ 应为负）。

因此：

• 奇数下标（$1, 3, 5, \dots$）为负数
• 偶数下标（$2, 4, 6, \dots$）为正数

且所有元素均非零。

---

第二步：正数绝对值下界推导

引理 1：任何正数 $a_i$ 必须满足 $|a_i| \ge 2$。

证明：考虑 $i = 1$ 或 $i = n$ 时，正数只有一个相邻负数。取长度为 $2$ 的子数组 $[a_{i-1}, a_i]$（或 $[a_i, a_{i+1}]$），该负数绝对值至少为 $1$（因为是整数非零），所以正数必须至少为 $2$ 才能保证和为正。

引理 2：若正数位于中间（$2 \le i \le n-1$），则必须满足 $|a_i| \ge 3$。

证明：考虑子数组 $[a_{i-1}, a_i, a_{i+1}]$。由于 $a_{i-1}$ 和 $a_{i+1}$ 都是负数，其绝对值至少为 $1$，所以：

$$a_{i-1} + a_i + a_{i+1} \le (-1) + a_i + (-1) = a_i - 2 $$

因为子数组和必须为正（至少为 $1$），所以：

$$a_i - 2 \ge 1 \quad \Rightarrow \quad a_i \ge 3$$

因此：

• 两端的正数（仅当 $n$ 为偶数时，最后一个元素 $a_n$ 是正数）可以取 $|a_i| = 2$
• 中间的正数（左侧和右侧都有负数）必须取 $|a_i| \ge 3$

---

第三步：贪心构造

为了使得 $[|a_1|, |a_2|, \dots, |a_n|]$ 字典序最小，我们从左到右贪心地取尽可能小的绝对值。

• $|a_1|$ 最小可取 $1$（负数），所以 $a_1 = -1$
• 对于偶数下标 $i$（正数）：
  • 若 $2 \le i \le n-1$（中间的正数），由引理 2，最小取 $3$
  • 若 $i = n$ 且 $n$ 为偶数（最后一个元素是正数），由引理 1，最小取 $2$
• 对于奇数下标 $i \ge 3$（负数），最小绝对值可取 $1$，所以 $a_i = -1$

构造结果：

$$a_i = \begin{cases} -1, & i \text{ 为奇数} \\ 3, & i \text{ 为偶数且 } 2 \le i \le n-1 \\ 2, & i = n \text{ 且 } n \text{ 为偶数} \end{cases} $$

---

第四步：验证数组是“好”的

条件 1：符号交替 ✓

条件 2（所有长度 $\ge 2$ 的子数组和为正）：

• 长度为 2：由一个正数（$\ge 2$）和一个负数（$-1$）组成，和 $\ge 1 > 0$ ✓
• 长度为 3：有两种情况：
  • 模式 $[-1, 3, -1]$：和为 $1 > 0$ ✓
  • 模式 $[3, -1, 3]$ 或 $[2, -1, 3]$ 等：两个正数（$\ge 2$）和一个负数（$-1$），和 $\ge 2 + 2 - 1 = 3 > 0$ ✓
• 长度 $k \ge 4$：至少有 $\lfloor \frac{k}{2} \rfloor$ 个正数（每个 $\ge 2$），至多有 $\lceil \frac{k}{2} \rceil$ 个负数（每个 $= -1$），因此：$$\text{和} \ge 2 \cdot \left\lfloor \frac{k}{2} \right\rfloor - 1 \cdot \left\lceil \frac{k}{2} \right\rceil $$当 $k$ 为偶数时：$\ge 2 \cdot \frac{k}{2} - \frac{k}{2} = \frac{k}{2} \ge 2$ 当 $k$ 为奇数时：$\ge 2 \cdot \frac{k-1}{2} - \frac{k+1}{2} = \frac{k-3}{2} \ge \frac{1}{2}$，由于是整数，$\ge 1$ ✓

因此所有子数组和为正。

---

第五步：最优性证明

构造过程是贪心的：每个位置上我们都取了满足所有约束的最小可能绝对值。由于约束只依赖于之前的位置（左侧子数组）以及相邻关系，贪心选择不会影响后续位置的可行性（可通过归纳法证明）。因此，得到的 $[|a_1|, |a_2|, \dots, |a_n|]$ 在所有好数组中字典序最小。

---

第六步：示例

$n$	构造结果	绝对值序列
2	$[-1, 2]$	$[1, 2]$
3	$[-1, 3, -1]$	$[1, 3, 1]$
4	$[-1, 3, -1, 2]$	$[1, 3, 1, 2]$
5	$[-1, 3, -1, 3, -1]$	$[1, 3, 1, 3, 1]$
6	$[-1, 3, -1, 3, -1, 2]$	$[1, 3, 1, 3, 1, 2]$

注意：对于 $n=5$，$a_4 = 3$（中间正数）而非 $2$，因为 $i=4$ 时 $2 \le i \le n-1$（$4 \le 4$ 成立），所以取 $3$。

---

C++ 实现

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) {
                // 奇数下标：填 -1
                cout << "-1";
            } else {
                // 偶数下标（正数）
                if (i == n && n % 2 == 0) {
                    // 最后一个元素是正数（n 为偶数时）
                    cout << "2";
                } else {
                    // 中间的正数
                    cout << "3";
                }
            }
            if (i < n) cout << " ";
        }
        cout << "\n";
    }
    
    return 0;
}