问题理解

我们需要构造一个长度为 $n$ 的排列，使得可以执行尽可能多的“缩操作”。

缩操作的定义：

• 选择一个下标 $i$（$2 \le i \le m-1$），满足 $a_i > a_{i-1}$ 且 $a_i > a_{i+1}$（即 $a_i$ 是严格局部最大值）
• 移除 $a_i$

目标：最大化可以执行的操作次数。

---

关键观察

1. 最大元素的位置
   在整个排列中，最大值 $n$ 只能出现一次。只要最大值 $n$ 不在两端（即不在第一个或最后一个位置），它就一定是局部最大值（因为所有其他元素都比它小）。因此，只要 $n$ 不在两端，它就可以被移除。

2. 移除后的变化
   当我们移除 $n$ 后，剩下的排列中会出现新的最大值（即 $n-1$）。同样地，只要 $n-1$ 不在当前数组的两端，它就可以被移除。

3. 过程持续
   这个过程可以一直持续，直到数组中只剩下两个元素。因为：

   • 当数组长度为 $2$ 时，没有下标 $i$ 满足 $2 \le i \le m-1$（因为 $m-1 = 1$）
   • 所以无法再执行任何操作

4. 最大操作次数
   初始数组长度为 $n$，最终数组长度为 $2$，每执行一次操作数组长度减少 $1$，因此最多可以执行：

   $$n - 2$$

   次操作。

---

如何达到最大操作次数？

我们需要让每次移除的都是当前的最大值。也就是说：

• 首先移除 $n$
• 然后移除 $n-1$
• 然后移除 $n-2$
• ...
• 最后移除 $3$

剩下的两个元素是 $1$ 和 $2$。

关键条件：每次要移除的最大值必须不在两端。

---

构造方法

一种简单的构造是：

• 把 $1$ 放在最后
• 把 $2$ 放在最前
• 其余数字 $3, 4, \dots, n$ 按顺序放在中间

即：

$$[2, 3, 4, \dots, n, 1]$$

验证：

• $n$ 在位置 $n-1$（从 $1$ 开始计数），左右都有元素 → 可以移除
• 移除 $n$ 后，$n-1$ 成为新的最大值，仍然在中间 → 可以移除
• 依此类推，直到剩下 $[2, 1]$

---

为什么这样可行？

在排列 $[2, 3, 4, \dots, n, 1]$ 中：

• 对于任意 $k$（$3 \le k \le n$），$k$ 的左边是 $k-1$，右边是 $k+1$（或当 $k=n$ 时右边是 $1$）
• 由于所有数字都不同，且 $k$ 是当前剩余元素中的最大值时，它一定大于左右邻居
• 因此 $k$ 满足局部最大值的条件，可以被移除

---

算法步骤

对于每个测试用例：

1. 输出 $2, 3, 4, \dots, n$
2. 最后输出 $1$

---

复杂度

• 时间复杂度：$O(n)$ 每个测试用例
• 空间复杂度：$O(1)$（不考虑输出）

---

代码实现

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    
    for (int i = 2; i <= n; i++) {
        cout << i << ' ';
    }
    cout << 1 << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

---

示例验证

示例 1：$n = 3$

• 输出：$2\ 3\ 1$
• 操作过程：
  • 移除 $3$（位置 $2$）：$[2, 1]$
  • 无法继续
  • 操作次数 = $1 = n - 2$ ✅

示例 2：$n = 6$

• 输出：$2\ 3\ 4\ 5\ 6\ 1$
• 可以执行 $4$ 次操作，达到最大值 $n - 2 = 4$ ✅

---

结论

任何满足 $1$ 和 $2$ 在两端的排列都能达到最大操作次数 $n-2$。最简单的构造是：

$$[2, 3, 4, \dots, n, 1]$$