P12973 一道搞笑的构造题

Many thanks to idea provider @[vegetable_king](https://www.luogu.com.cn/user/477443)! ------ 构造题真的有那么难吗？

设 $a$ 是一个序列，定义 $\operatorname{MEX}(a)$ 为 $a$ 中最小没有出现的正整数，$a[l, r]$ 为 $a$ 的第 $l$ 项到 $a$ 的第 $r$ 项组成的连续子序列。 给你 $n$，让你构造一个 $1 \sim n$ 的排列 $a$，使得 $$ \sum\limits_{l = 1}^n \sum\limits_{r = l}^n \operatorname{MEX}(a[l, r]) $$ 的值最大。（如果看不懂可以看题目末尾） 如果有多个 $a$ 的构造方案，请你输出字典序最小的一个。

第一行一个整数 $t$，表示数据组数。 对于每组数据，第一行一个整数 $n$。

对于每一个数据输出一行，表示你构造出来的 $a$。

**【样例解释】** 对于第二组测试数据（$n=2$）： $a[1, 1] = \{1\}$，最小没有出现的正整数是 $2$。 $a[2, 2] = \{2\}$，最小没有出现的正整数是 $1$。 $a[1, 2] = \{1, 2\}$，最小没有出现的正整数是 $3$。 上述式子的值为 $2 + 1 + 3 = 6$。 对于第三组测试数据（$n=3$）： $a[1, 1] = \{2\}$，最小没有出现的正整数是 $1$。 $a[2, 2] = \{1\}$，最小没有出现的正整数是 $2$。 $a[3, 3] = \{3\}$，最小没有出现的正整数是 $1$。 $a[1, 2] = \{2, 1\}$，最小没有出现的正整数是 $3$。 $a[2, 3] = \{1, 3\}$，最小没有出现的正整数是 $2$。 $a[1, 3] = \{2, 1, 3\}$，最小没有出现的正整数是 $4$。 上述式子的值为 $1 + 2 + 1 + 3 + 2 + 4 = 13$。 可以证明，没有其他的排列可以使得上述式子的值比答案更大，且没有其他的排列可以使得上述式子的值与答案相等的同时字典序比答案小。 **【数据范围】** 记一个测试点所有的 $n$ 之和为 $\sum n$。 对于 $30\%$ 的数据：$\sum n \le 9$。 对于 $100\%$ 的数据：$1 \le n \le 10^6$，$1 \le t \le 10^6$，$\sum n \le 10^6$。 **【温馨提示】** $$ \sum\limits_{l = 1}^n ( \sum\limits_{r = l}^n \operatorname{MEX}(a[l, r])) $$ 的伪代码如下： ``` for each l in range(1,n): for each r in range(l,n): result = result+MEX(l,r) ``` 最终结果为 $result$。