Different medians

 This was a medium kind of problem and basically I had to understand the pattern that was hidden in the Results, although this was still tricky if we try to get it's core idea, like how we are getting the condition that was required by using a particular order of elements, and according to me this would be more difficult if the elements would be random instead of being in a range from 1 to N. Well, overall I did this problem too in just 1 execution and it passed all the Test Cases. And I think I took around 30 mins for this 1.

Try to make your own sample cases and try to figure out some idea on the basis of your understanding, just try test and try that's it.

Here is the Problem Statement for your perusal:

Problem Statement:-

Chef is given an integer $�$. Chef wants to construct a permutation $�=[{�}_1,{�}_2,\dots ,{�}_{�}]$ of $\{1,2,3,\dots ,�\}$ that satisfies the following condition:

• Let ${�}_{�}$ denote the prefix of $�$ of length $�$, i.e, ${�}_{�}=[{�}_1,{�}_2,\dots ,{�}_{�}]$. Then, for every $1\le �<�$, it must hold that $\text{median}({�}_{�})\mathrm{\ne }\text{median}({�}_{�+1})$

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

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

• Let $�$ be an ($1$-indexed) array of length $�$. Let $�$ be the array obtained by sorting $�$. Then $\text{median}(�)$ is defined to be ${�}_{\lceil \frac{�}{2}\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 $�$, denoting the number of test cases.
• The first and only line of each test case contains a single integer $�$.

Output Format

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

Constraints

• $1\le �\le 30$
• $2\le �\le 1000$
• The sum of $�$ over all test cases won't exceed $1000$.

Sample 1:

Input

Output

2
2
3

2 1
2 1 3

Explanation:

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

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

Explanation:-

Simply, all the observations, all the testing of the sample cases and testing on the basis of our own Sample Cases every test boils down to one simple logic.

 The logic is that we just have to start from the last index of the resulting array(if we store the resulting permutation in a list) and maintain 2 iterable variables(itr1 and itr2) and whenever we get an odd index just use itr1 which starts with 1 and is incremented after every usage, and if we get an even index then we just use the itr2 variable which starts with n and decreases after every usage. That's it!

You should first try to understand the Cases on your own before implementing this idea because if you simply use my idea then you won't be able to completely understand the core of this Problem. 

Peace!!

Code Implementation:-

for _ in range(int(input())):

    n=int(input())

    ans=[0]*n

    itr1=1

    itr2=n    

    for i in range(n-1,-1,-1):

        if(i%2!=0):

            ans[i]=itr1

            itr1+=1

        else:

            ans[i]=itr2

            itr2-=1

    print(*ans)