← 返回题目列表

Codeforces · 2117/B

B. 收缩

中文机器翻译题面 查看原题

对大小为 $$$m$$$ 的数组 $$$a$$$ 的收缩操作定义如下:

  • 选择索引 $$$i$$$ ($$$2 \le i \le m - 1$$$) 使得 $$$a_i \gt a_{i - 1}$$$ 和 $$$a_i \gt a_{i + 1}$$$。
  • 从数组中删除 $$$a_i$$$。

定义 分数 本实验的 的排列$$$^{\text{∗}}$$$ $$$p$$$ 作为 最大 可以对 $$$p$$$ 执行收缩操作的次数。

Yousef 给了你一个整数 $$$n$$$。构造一个长度为 $$$n$$$ 的排列 $$$p$$$ ,其中 最大 可能 分数 本实验的。如果有多个答案,则可以输出其中任何一个。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。

每个测试用例包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 排列的大小。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出最大化收缩操作数量的任意排列 $$$p_1, p_2, \dots, p_n$$$。

示例

输入
复制

2
3
6

输出
复制

1 3 2
2 3 6 4 5 1

注意

在第一个测试用例中:

  • 我们选择 $$$p = [1, 3, 2]$$$。
  • 选择索引 $$$2$$$,并从数组中删除 $$$p_2$$$。该数组变为 $$$p = [1, 2]$$$。

可以看出,我们可以执行的最大操作数是$$$1$$$。另一个有效答案是 $$$p = [2, 3, 1]$$$。

在第二个测试用例中:

  • 我们选择 $$$p = [2, 3, 6, 4, 5, 1]$$$。
  • 选择索引 $$$5$$$,并从数组中删除 $$$p_5$$$。该数组变为 $$$p = [2, 3, 6, 4, 1]$$$。
  • 选择索引 $$$3$$$,并从数组中删除 $$$p_3$$$。该数组变为 $$$p = [2, 3, 4, 1]$$$。
  • 选择索引 $$$3$$$,并从数组中删除 $$$p_3$$$。该数组变为 $$$p = [2, 3, 1]$$$。
  • 选择索引 $$$2$$$,并从数组中删除 $$$p_2$$$。该数组变为 $$$p = [2, 1]$$$。

我们可以执行的最大操作数是$$$4$$$。任何得分为 $$$4$$$ 的排列都是有效的。