Constructing the Array

题意翻译

给你一个 $n$$(n \leq 200000)$ ,有一串长度为 $n$ 的空串 $a$ （全是 $0$ ），你可以进行 $n$ 次操作，每第 $i$ 次操作确定一个 $l$ 和一个 $r$ 为当前串里最长连续 $0$ 串的左右端点，如果 $r-l+1$ 是奇数，那么第 $\frac{l+r}{2}$ 个数就更新为 $i$ ，否则第 $\frac{l+r-1}{2}$ 个数就更新成 $i$ 。以此类推。最后要求你输出 $n$ 次更新后的新串。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

6
1
2
3
4
5
6

输出样例 #1

1 
1 2 
2 1 3 
3 1 2 4 
2 4 1 3 5 
3 4 1 5 2 6