Day3——B
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:

Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;
Let this segment be [l;r]. If r−l+1 is odd (not divisible by 2) then assign (set) a[l+r2]:=i (where i is the number of the current action), otherwise (if r−l+1 is even) assign (set) a[l+r−12]:=i.
Consider the array a of length 5 (initially a=[0,0,0,0,0]). Then it changes as follows:

Firstly, we choose the segment [1;5] and assign a[3]:=1, so a becomes [0,0,1,0,0];
then we choose the segment [1;2] and assign a[1]:=2, so a becomes [2,0,1,0,0];
then we choose the segment [4;5] and assign a[4]:=3, so a becomes [2,0,1,3,0];
then we choose the segment [2;2] and assign a[2]:=4, so a becomes [2,4,1,3,0];
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
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (1≤n≤2⋅105) — the length of a.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 (∑n≤2⋅105).

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

Example
Input
6
1
2
3
4
5
6
Output
1
1 2
2 1 3
3 1 2 4
2 4 1 3 5
3 4 1 5 2 6

题意：找到一个数组满足：
1、选择最大的长度子数组(连续子段)由只在所有这样的段中，选择最左边一个；
2、让这段[l;r][l;r]。如果r−l+1r−l+1是奇数然后分配a[l+r2]:=ia[l+r2]:=i，则为赋值a[l+r−12]:=ia[l+r−12]:=i

思路：
优先队列，将0序列的长度和左右端点放入优先队列中，注意重写<

代码如下

include<iostream>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
int ans[maxn];
struct node
{
    int l,r;
    node() {}
    node(int ll,int rr):l(ll),r(rr) {}
};
struct cmp
{
    bool operator()(node a,node b)
    {
        if(a.r-a.l!=b.r-b.l)
            return (a.r-a.l)<(b.r-b.l);   
        else
            return a.l>b.l;
    }
};
priority_queue<node,vector<node>,cmp > q;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        q.push(node(1,n));
        int cnt=1;
        while(!q.empty())
        {
            node tmp=q.top();
            q.pop();
            int mid=(tmp.l+tmp.r)/2;
            ans[mid]=cnt++;
            if(mid-1>=tmp.l)
                q.push(node(tmp.l,mid-1));
            if(mid+1<=tmp.r)
                q.push(node(mid+1,tmp.r));
        }
        for(int i=1; i<=n; i++)
        {
            if(i!=1)
                cout<<" ";
            cout<<ans[i];
        }
        cout<<endl;
    }
}