← 返回题目列表

Codeforces · 1754/B

B. 凯文和排列

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

在他的生日那天,凯文收到了一组成对的不同数字 $$$1, 2, 3, \ldots, n$$$ 作为礼物。

他将以某种方式排列这些数字,使两个连续数字之间的绝对差值尽可能最小。更正式地说,如果他按照 $$$p_1, p_2, \ldots, p_n$$$ 的顺序排列数字,他想要最大化 $$$$$$\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert,$$$$$$ 的值,其中 $$$|x|$$$ 表示 $$$x$$$ 的绝对值。

帮助凯文做到这一点。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \le n \leq 1\,000$$$) — 集合的大小。

输出

对于每个测试用例,打印一行,其中包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) 描述最大化连续元素的最小绝对差的排列。

正式地,您必须打印一个排列 $$$p$$$ ,该排列使值 $$$\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert$$$ 最大化。

如果有多个最优解,则打印其中任意一个。

示例

输入 #1

2
4
3

输出 #1

2 4 1 3
1 2 3

注意

在第一个测试用例中,连续元素的最小绝对差等于 $$$\min \{\lvert 4 - 2 \rvert, \lvert 1 - 4 \rvert, \lvert 3 - 1 \rvert \} = \min \{2, 3, 2\} = 2$$$。很容易证明这个答案是最优的。

在第二个测试用例中,数字 $$$1, 2, 3$$$ 的每个排列都是最佳答案。连续元素的最小绝对差等于$$$1$$$。