codeforces#P1754B. Kevin and Permutation
Kevin and Permutation
Description
For his birthday, Kevin received the set of pairwise distinct numbers $1, 2, 3, \ldots, n$ as a gift.
He is going to arrange these numbers in a way such that the minimum absolute difference between two consecutive numbers be maximum possible. More formally, if he arranges numbers in order $p_1, p_2, \ldots, p_n$, he wants to maximize the value $$\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert,$$ where $|x|$ denotes the absolute value of $x$.
Help Kevin to do that.
Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Description of the test cases follows.
The only line of each test case contains an integer $n$ ($2 \le n \leq 1\,000$) — the size of the set.
For each test case print a single line containing $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) describing the arrangement that maximizes the minimum absolute difference of consecutive elements.
Formally, you have to print a permutation $p$ which maximizes the value $\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert$.
If there are multiple optimal solutions, print any of them.
Input
Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Description of the test cases follows.
The only line of each test case contains an integer $n$ ($2 \le n \leq 1\,000$) — the size of the set.
Output
For each test case print a single line containing $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) describing the arrangement that maximizes the minimum absolute difference of consecutive elements.
Formally, you have to print a permutation $p$ which maximizes the value $\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert$.
If there are multiple optimal solutions, print any of them.
2
4
3
2 4 1 3
1 2 3
Note
In the first test case the minimum absolute difference of consecutive elements equals $\min \{\lvert 4 - 2 \rvert, \lvert 1 - 4 \rvert, \lvert 3 - 1 \rvert \} = \min \{2, 3, 2\} = 2$. It's easy to prove that this answer is optimal.
In the second test case each permutation of numbers $1, 2, 3$ is an optimal answer. The minimum absolute difference of consecutive elements equals to $1$.