# [Solution] Different Medians solution codechef

Different Medians solution codechef – Chef is given an integer N. Chef wants to construct a permutation A = [A_1, A_2, \ldots, A_N] of \{1, 2, 3, \ldots, N \} that satisfies the following condition:

• Let P_i denote the prefix of A of length i, i.e, P_i = [A_1, A_2, \ldots, A_i]. Then, for every 1 \leq i \lt N, it must hold that \text{median}(P_i) \neq \text{median}(P_{i+1})

## [Solution] Different Medians solution codechef

Help Chef find such a permutation A. If multiple answers exist, you may print any of them.

Note: The median of an array is defined as follows:

• Let A be an (1-indexed) array of length N. Let B be the array obtained by sorting A. Then \text{median}(A) is defined to be B_{\left\lceil \frac{N}{2}\right\rceil}. For example, \text{median}(\{3, 1, 2\}) = 2, and \text{median}(\{3, 4, 1, 2\}) = 2

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first and only line of each test case contains a single integer N.

### Output Format

For each test case, output the required permutation. If multiple answers are possible, you may print any of them.

## [Solution] Different Medians solution codechef

• 1 \leq T \leq 30
• 2 \leq N \leq 1000
• The sum of N over all test cases won’t exceed 1000.

### Sample 1:

Input

Output

2
2
3

2 1
2 1 3


## Different Medians solution codechef Explanation:

Test case 1: The prefixes of the given permutation are  and [2, 1], with medians 2 and 1 respectively.

Test case 2: The prefixes of the given permutation are  (with median 2), [2, 1] (with median 1), and [2, 1, 3] (with median 2). No two adjacent medians are equal.