CF2218C The 67th Permutation Problem

到校后，Macaque 被朋友 AG-88301 粗鲁地打了个招呼。AG-88301 因为整晚都在和一个毫无戒心的陌生人喋喋不休地讲述自己对 Collatz 猜想的开创性证明以及自己第 $67$ 个得不到回应的心动对象，结果没写作业。所以，按照惯例，AG-88301 让 Macaque 替他做作业，而且对感激和谢意的表现越来越少。Macaque 实在忍无可忍，于是转向他的“爪牙”（你们！）来替 AG-88301 解答作业。 你获得一个整数 $n$。你需要构造一个长度为 $3n$ 的排列，使得如果将这个排列划分为 $n$ 个连续的、各包含 $3$ 个元素的区块，这些区块的中位数之和最大。 更正式地说，你需要构造一个长度为 $3n$ 的排列 $p$，使得 $\sum_{i=0}^{n-1}\operatorname{median}(a_{3i+1},a_{3i+2},a_{3i+3})$ 最大。若有多个符合条件的 $p$，输出任意一个。 $\ast$ 长度为 $n$ 的排列是由 $1$ 到 $n$ 这 $n$ 个互不相同的整数按任意顺序排列得到的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（数组里 $2$ 出现了两次），又如 $[1,3,4]$ 也不是（长度应该为 $n=3$，但却有 $4$ 这个元素）。 $\dagger$ 一个包含 $3$ 个元素的数组 $b$ 的中位数是指，当 $b$ 按非递减顺序排序后，第 $2$ 个元素。

每组测试数据包含多组测试用例。第一行为测试用例个数 $t$，满足 $1 \le t \le 10^4$。接下来每组测试用例一行，包含一个整数 $n$，满足 $1 \leq n \leq 10^5$。 保证所有测试用例满足 $3n$ 的和不超过 $3 \cdot 10^5$。

对于每组测试用例，输出一个排列 $p$，使得每个连续长度为 $3$ 的区块中位数的和最大。若有多组解，输出任意一组即可。

在第一个样例中，$[1,3,4,2,5,6]$ 是一个可行答案，因为 $\operatorname{median}(1,3,4) + \operatorname{median}(2,5,6) = 3+5=8$，并且可以证明 $8$ 已经是最大可能的中位数和。 在第二个样例中，$[3,1,2]$ 是一个可行答案，因为 $n=1$，唯一能够取得的中位数和就是 $2$。 由 ChatGPT 5 翻译