## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Different Medians CodeChef Solution

## Problem

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})$

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

Solution Click Below:-  👉
👇👇👇👇👇

• 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.

### 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.