B. 收缩
每个测试点时间限制:2 秒
内存限制:256 兆字节
对于一个长度为 m 的数组 a,定义收缩操作如下:
- 选择一个下标 i(2≤i≤m−1),使得 ai>ai−1 且 ai>ai+1。
- 删除 ai。
定义一个排列 p 的得分为:在 p 上最多能执行多少次收缩操作。
Yousef 给你一个整数 n。请构造一个长度为 n 的排列 p,使其得分最大。如果有多个答案,输出任意一个即可。
*排列是长度为 n 的数组,包含 1 到 n 这 n 个不同的整数,顺序任意。例如,[2,3,1,5,4] 是一个排列,但 [1,2,2] 不是(2 出现两次),[1,3,4] 也不是(n=3 但数组中有 4)。
输入格式
第一行输入一个整数 t(1≤t≤103),表示测试用例的数量。
每个测试用例包含一个整数 n(3≤n≤2⋅105),表示排列的长度。
保证所有测试用例的 n 之和不超过 2⋅105。
输出格式
对于每个测试用例,输出任意一个排列 p1,p2,…,pn,使得收缩操作的次数最大。
示例
输入:
2
3
6
输出(可能不唯一):
1 3 2
2 3 6 4 5 1
样例解释
第一个测试用例(n=3):
- 选择 p=[1,3,2]
- 选择下标 2,删除 p2,数组变为 [1,2]
- 可以证明最大操作次数为 1。
另一个有效答案是 [2,3,1]。
第二个测试用例(n=6):
- 选择 p=[2,3,6,4,5,1]
- 选择下标 5(值为 5),删除后得到 [2,3,6,4,1]
- 选择下标 3(值为 6),删除后得到 [2,3,4,1]
- 选择下标 3(值为 4),删除后得到 [2,3,1]
- 选择下标 2(值为 3),删除后得到 [2,1]
- 最大操作次数为 4。任意得分为 4 的排列都是有效答案。