Constructing the Array
Contest: Codeforces Round 642 (Div. 3)
Difficulty rating: 1600
Tags: constructive algorithms, data structures, sortings

You are given an array $$$a$$$ of length $$$n$$$ consisting of zeros. You perform $$$n$$$ actions with this array: during the $$$i$$$-th action, the following sequence of operations appears:

1. Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;
2. Let this segment be $$$[l; r]$$$. If $$$r-l+1$$$ is odd (not divisible by $$$2$$$) then assign (set) $$$a[\frac{l+r}{2}] := i$$$ (where $$$i$$$ is the number of the current action), otherwise (if $$$r-l+1$$$ is even) assign (set) $$$a[\frac{l+r-1}{2}] := i$$$.

Consider the array $$$a$$$ of length $$$5$$$ (initially $$$a=[0, 0, 0, 0, 0]$$$). Then it changes as follows:

1. Firstly, we choose the segment $$$[1; 5]$$$ and assign $$$a[3] := 1$$$, so $$$a$$$ becomes $$$[0, 0, 1, 0, 0]$$$;
2. then we choose the segment $$$[1; 2]$$$ and assign $$$a[1] := 2$$$, so $$$a$$$ becomes $$$[2, 0, 1, 0, 0]$$$;
3. then we choose the segment $$$[4; 5]$$$ and assign $$$a[4] := 3$$$, so $$$a$$$ becomes $$$[2, 0, 1, 3, 0]$$$;
4. then we choose the segment $$$[2; 2]$$$ and assign $$$a[2] := 4$$$, so $$$a$$$ becomes $$$[2, 4, 1, 3, 0]$$$;
5. and at last we choose the segment $$$[5; 5]$$$ and assign $$$a[5] := 5$$$, so $$$a$$$ becomes $$$[2, 4, 1, 3, 5]$$$.

Your task is to find the array $$$a$$$ of length $$$n$$$ after performing all $$$n$$$ actions. Note that the answer exists and unique.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output format:
For each test case, print the answer — the array $$$a$$$ of length $$$n$$$ after performing $$$n$$$ actions described in the problem statement. Note that the answer exists and unique.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
6
1
2
3
4
5
6

Example output:
1 
1 2 
2 1 3 
3 1 2 4 
2 4 1 3 5 
3 4 1 5 2 6

Editorial:
This is just an implementation problem. We can use some kind of heap or ordered set to store all segments we need in order we need. To solve this problem on C++ with std::set, we can just rewrite the comparator for std::set like this:
And then just write the std::set like this:
Now the minimum element of the set will be the segment that we need to choose. Initially, the set will contain only one segment $$$[0;n-1]$$$. Suppose we choose the segment $$$[l; r]$$$ during the $$$i$$$-th action. Let $$$id = \lfloor\frac{l+r}{2}\rfloor$$$, where $$$\lfloor\frac{x}{y}\rfloor$$$ is $$$x$$$ divided by $$$y$$$ rounded down. Assign (set) $$$a[id] := i$$$, then if the segment $$$[l; id-1]$$$ has positive (greater than zero) length, push this segment to the set and the same with the segment $$$[id+1;r]$$$. After $$$n$$$ such actions we get the answer.
Time complexity: $$$O(n \log n)$$$.