Given a sequence of N elements, Chef defines a function F(i) (1 ≤ i ≤ N) as the median of the first i elements of the sequence.

Chef wants to get a *permutation* P of length N such that P_{i} = F(i) \forall 1 ≤ i ≤ N. Can you help Chef in achieving this?

Note that:
The *median* of a sequence is the middle element in the sorted order of the sequence. If N is even, choose the element at \frac{N}{2} position in the sorted order. If N is odd, choose the middle element.
A *permutation* of length N is an array of N integers P = [P_{1}, P_{2}, \ldots, P_{N}] such that every integer from 1 to N (inclusive) appears in it exactly once. For example, [2,5,4,1,3] is a permutation of length 5 while [2, 5, 2, 1, 3] is not.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follows.
- Each test case consists of a single line of input, an integer N, the length of the required permutation.

------ Output Format ------ 

For each test case, output in a new line, N space-separated integers, denoting a *permutation* satisfying the condition.

------ Constraints ------ 

$1 ≤ T ≤ 700$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
1
2
3

----- Sample Output 1 ------ 
1
2 1 
3 1 2
----- explanation 1 ------ 
Test Case $1$: $[1]$ is the only permutation and it satisfies the condition as the median of the sequence $[1]$ is $1$.

Test Case $2$: The possible permutations of length $2$ are $[1, 2]$ and $[2, 1]$. The only permutation that satisfies the condition is $[2, 1]$. Here, $P_{1} = 2 = median([2])$ and $P_{2} = 1 = median([2, 1])$.

Test Case $3$: There are $6$ possible permutations out of which only $[3,1,2]$ satisfies the above condition.  Here, $P_{1} = 3 = median([3]), P_{2} = 1 = median([3, 1]),$ and $P_{3} = 2 = median([3, 1, 2])$.

Difficulty: EASY
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
t = int(input())
for ni in range(t):
	n = int(input())
	(i, j) = (1, n)
	while i <= j:
		print(j, end=' ')
		if i != j:
			print(i, end=' ')
		i = i + 1
		j = j - 1
	print(' ')


for _ in range(int(input())):
	n = int(input())
	l = []
	(i, j) = (1, n)
	while i <= j:
		print(j, end=' ')
		if i != j:
			print(i, end=' ')
		i = i + 1
		j = j - 1
	print()


for _ in range(int(input())):
	n = int(input())
	(li, ri, i) = (n, 0, 1)
	while li > ri:
		if i % 2:
			print(li, end=' ')
			li -= 1
		else:
			ri += 1
			print(ri, end=' ')
		i += 1
	print()


for i in range(int(input())):
	n = int(input())
	a = 1
	b = n
	for i in range(a, n + 1):
		if i % 2 == 0:
			print(a, end=' ')
			a = a + 1
		else:
			print(b, end=' ')
			b = b - 1
	print()


for _ in range(int(input())):
	N = int(input())
	A = [0] * N
	for i in range(0, N, 2):
		A[i] = N - i // 2
		if i <= N - 2:
			A[i + 1] = i // 2 + 1
	print(*A)


for _ in range(int(input())):
	n = int(input())
	k = n
	j = 1
	p = []
	for i in range(1, n + 1):
		if i % 2 != 0:
			p.append(k)
			k -= 1
		else:
			p.append(j)
			j += 1
	print(*p)


def solve():
	n = int(input())
	p = n // 2 + 1
	k = n - p
	if n % 2:
		for i in range(k, 0, -1):
			print(p + i, p - i, end=' ')
		print(p)
	else:
		for i in range(k, -1, -1):
			print(p + i, p - i - 1, end=' ')
		print()
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	l1 = []
	n = int(input())
	r = range(1, n + 1)
	for x in range(n // 2):
		l1.append(r[~x])
		l1.append(r[x])
	if n % 2 == 1:
		l1.append(n // 2 + 1)
	print(' '.join(map(str, l1)))


for tc in range(int(input())):
	n = int(input())
	p = list(range(1, n + 1))
	i = 0
	j = n - 1
	new = []
	while i <= j:
		new.append(p[j])
		if i != j:
			new.append(p[i])
		j -= 1
		i += 1
	print(*new)


def per_arr(val):
	res = []
	if val % 2 == 0:
		pivot = val // 2
		for i in range(val):
			if i % 2 == 0:
				res.append(pivot - (i + 1) // 2)
			else:
				res.append(pivot + (i + 1) // 2)
	else:
		pivot = val // 2 + 1
		for i in range(val):
			if i % 2 == 0:
				res.append(pivot + (i + 1) // 2)
			else:
				res.append(pivot - (i + 1) // 2)
	return reversed(res)
N = int(input())
for _ in range(N):
	val = int(input())
	print(*per_arr(val))


for _ in range(int(input())):
	N = int(input())
	l = 1
	r = N
	while l <= r:
		print(r, end=' ')
		if l != r:
			print(l, end=' ')
		l += 1
		r -= 1
	print()


import math
for i in range(int(input())):
	n = int(input())
	l1 = [i for i in range(1, n // 2 + 1)]
	l2 = [i for i in range(n, math.ceil(n // 2), -1)]
	ans = []
	m = max(len(l1), len(l2))
	for i in range(m):
		if i < len(l2):
			ans.append(l2[i])
		if i < len(l1):
			ans.append(l1[i])
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	mid = n
	beg = 1
	for i in range(n):
		if i % 2 == 0:
			print(mid, end=' ')
			mid -= 1
		else:
			print(beg, end=' ')
			beg += 1
	print()


for _ in range(int(input())):
	n = int(input())
	(beg, end) = (1, n)
	arr = []
	for i in range(n):
		if i % 2 == 0:
			arr.append(end)
			end -= 1
		else:
			arr.append(beg)
			beg += 1
	print(*arr)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [i + 1 for i in range(n)]
	i = 0
	j = n - 1
	b = []
	while i < j:
		b.append(a[j])
		b.append(a[i])
		j -= 1
		i += 1
	if i == j:
		b.append(a[i])
	print(' '.join(map(str, b)))


t = int(input())
while t > 0:
	n = int(input())
	i = 1
	while n >= i:
		if n != i:
			print(n, end=' ')
			print(i, end=' ')
		if n == i:
			print(n, end='')
		n -= 1
		i += 1
	print('')
	t -= 1


import sys, math, bisect, heapq, collections, itertools, functools
inum = lambda : int(sys.stdin.readline())
imap = lambda : map(int, sys.stdin.readline().split())
itup = lambda : tuple(map(int, sys.stdin.readline().split()))
isor = lambda : sorted(map(int, sys.stdin.readline().split()))
isor2 = lambda nums: sorted(nums, key=lambda num1: (num1[0], num1[1]))
ilis = lambda : [int(zz) for zz in sys.stdin.readline().split()]
dd = lambda : collections.defaultdict(lambda : 0)
adjlist = lambda : collections.defaultdict(lambda : [])
lcm = lambda num1, num2: num1 * num2 // math.gcd(num1, num2)
npr = lambda num1, num2: math.factorial(num1) // math.factorial(num1 - num2)
lowerpower = lambda num1, num2: pow(num2, math.floor(math.log(num1, num2)))
upperpower = lambda num1, num2: pow(num2, math.ceil(math.log(num1, num2)))
isperfectsquare = lambda num1: math.ceil(math.log(num1, 2)) == math.floor(math.log(num1, 2))
ncr = lambda num1, num2: math.factorial(num1) // (math.factorial(num2) * math.factorial(num1 - num2))
filtereven = lambda nums: list(filter(lambda num1: num1 % 2 == 0, nums))
filteroddd = lambda nums: list(filter(lambda num1: num1 % 2 != 0, nums))
fact = lambda num1: functools.reduce(lambda num2, num3: num2 * num3, range(1, num1 + 1))
freqarray = lambda nums: collections.Counter(nums)
bitsetarray = lambda nums: [int(num1) for num1 in bin(nums)[2:]]
lengthbitset = lambda num1: math.ceil(math.log(num1 + 0.1, 2))
bit_check = lambda num1, num2: num1 & 1 << num2
bit_set = lambda num1, num2: num1 | 1 << num2
bit_unset = lambda num1, num2: num1 & ~(1 << num2)
bit_toggle = lambda num1, num2: num1 ^ 1 << num2
minheap = lambda nums: 1 if heapq.heapify(nums) == None else 0
maxheap = lambda nums: 1 if heapq._heapify_max(nums) == None else 0
lowerbound = lambda nums, key, start, stop: bisect.bisect_left(nums, key, lo=start, hi=stop)
upperbound = lambda nums, key, start, stop: bisect.bisect_right(nums, key, lo=start, hi=stop)
inorder = lambda root: inorder(root.left) + [root.val] + inorder(root.right) if root else []
prefixsumarray = lambda nums: list(itertools.accumulate(nums, lambda num1, num2: num1 + num2))
suffixsumarray = lambda nums: prefixsum(reversed(nums))
grid = lambda rows, cols: [[0 for j in range(cols)] for idx in range(rows)]
palindromeindices = lambda num1: [(num1 // 2 - i - (0 if num1 & 1 else 1), num1 // 2 + i) for i in range(num1 // 2 + (1 if num1 & 1 else 0))]
onum = lambda num1: '%d' % num1
omap = lambda num1, num2: '%d %d' % (num1, num2)
olis = lambda nums: ' '.join((str(nums[idx]) for idx in range(len(nums))))
odict = lambda nums: '\n'.join((str('%idx: %s' % (num1[0], ' '.join((str(num2) for num2 in num1[1])))) for num1 in zip(nums.keys(), nums.values())))
ogrid = lambda grid: '\n'.join((' '.join((str(num1) for num1 in nums)) for nums in grid))
tcs = 1 if not True else int(input())
for tc in range(1, tcs + 1):
	n = inum()
	beg = 1
	mid = n
	ans = []
	for i in range(n):
		if i % 2 == 0:
			ans.append(mid)
			mid -= 1
		else:
			ans.append(beg)
			beg += 1
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	n = [i for i in range(1, n + 1)]
	i = 0
	k = len(n) - 1
	p = {}
	while i != len(n) or k != -1:
		try:
			p[n[k]] = 0
			k -= 1
			p[n[i]] = 0
			i += 1
		except:
			pass
	print(*p.keys())


for _ in range(int(input())):
	n = int(input())
	l = 1
	r = n
	for i in range(1, n + 1):
		if i % 2 == 0:
			print(l, end=' ')
			l += 1
		else:
			print(r, end=' ')
			r -= 1
	print()


T = int(input())
for t in range(T):
	N = int(input())
	arr = [0] * N
	counter = N
	for i in range(0, len(arr), 2):
		arr[i] = counter
		counter -= 1
	start = 0
	if arr[-1] == 0:
		start = len(arr) - 1
	else:
		start = len(arr) - 2
	for i in range(start, 0, -2):
		arr[i] = counter
		counter -= 1
	for i in range(N):
		print(arr[i], end=' ')
	print()


def solve():
	len = int(input())
	p = list(range(1, len + 1))
	ans = []
	for (i, j) in zip(list(range(0, len)), list(range(len - 1, -1, -1))):
		if abs(j - i) == 1:
			ans.append(p[j])
			ans.append(p[i])
			break
		if abs(j - i) == 0:
			ans.append(p[j])
			break
		ans.append(p[j])
		ans.append(p[i])
	print(*ans)
run = int(input())
while run:
	solve()
	run -= 1


for tc in range(int(input())):
	n = int(input())
	x = list(range(1, n + 1))
	r = []
	for i in range(n):
		if x != []:
			r.append(x.pop())
			if x != []:
				r.append(x.pop(0))
	for e in r:
		print(e, end=' ')
	print()


for i in range(int(input())):
	k = int(input())
	l = [x for x in range(1, k + 1)]
	ans = []
	for j in range(k):
		if j % 2 == 0:
			ans.append(l[-1 - j // 2])
		else:
			ans.append(l[j // 2])
	for w in range(k):
		print(ans[w], end=' ')
	print()


n = int(input())
for i in range(n):
	a = int(input())
	i = 1
	j = a
	l = []
	while i < j:
		l.append(j)
		l.append(i)
		i = i + 1
		j = j - 1
	if i == j:
		l.append(i)
	print(*l)


t = int(input())
for i in range(t):
	n = int(input())
	lx = []
	i = 1
	j = n
	while i < j:
		lx.append(j)
		lx.append(i)
		i += 1
		j -= 1
	if i == j:
		lx.append(i)
	print(*lx)


a = int(input())
for i in range(a):
	b = int(input())
	c = []
	d = 1
	e = b
	while d < e:
		c.append(e)
		c.append(d)
		d += 1
		e -= 1
	if d == e:
		c.append(d)
	print(*c)


for i in range(int(input())):
	l = []
	N = int(input())
	for j in range(N // 2):
		print(N - j, j + 1, end=' ')
	if N % 2 == 1:
		print((N + 1) // 2)
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for j in range(n):
		if j % 2 == 0:
			a.append(n - j // 2)
		else:
			a.append((j + 1) // 2)
	print(*a)


n = int(input())
for i in range(n):
	N = int(input())
	arr = []
	k = N
	for j in range(0, N):
		if j % 2 == 0:
			arr.append(k - j // 2)
		else:
			arr.append((j + 1) // 2)
	print(*arr)


t = int(input())
for _ in range(t):
	length = int(input())
	max_val = length
	start = 1
	while start <= max_val:
		if start == max_val:
			print(start, end='')
			break
		print(f'{max_val} {start} ', end='')
		max_val -= 1
		start += 1
	print()


t = int(input(''))
for i in range(t):
	n = int(input())
	s = list(range(1, n + 1))
	a = []
	while len(s) != 0:
		if len(s) % 2 == 0:
			a.append(s[len(s) // 2 - 1])
			s.pop(len(s) // 2 - 1)
		else:
			a.append(s[len(s) // 2])
			s.pop(len(s) // 2)
	a.reverse()
	for i in a:
		print(i, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	arr = []
	i = 0
	while i < n:
		if i % 2 == 0:
			arr.append(n - i // 2)
		else:
			arr.append((i + 2) // 2)
		i = i + 1
	print(*arr)


for s in range(int(input())):
	x = int(input())
	(p, x2) = ([], 0)
	for k in range(1, x + 1):
		if k % 2 == 1:
			p.append(x - x2)
			x2 += 1
		else:
			p.append(x2)
	print(*p, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	res = []
	if n % 2 == 0:
		b = n // 2
	else:
		b = n // 2 + 1
	x = n
	y = 1
	for i in range(b):
		if x != y:
			res.append(x)
			res.append(y)
		else:
			res.append(x)
		x -= 1
		y += 1
	print(*res, ' ')


t = int(input())
for i in range(t):
	n = int(input())
	t1 = n
	t2 = 1
	l = []
	i = 0
	while i < n:
		l.append(t1)
		t1 = t1 - 1
		i = i + 1
		if i < n:
			l.append(t2)
			t2 = t2 + 1
			i = i + 1
	for i in range(n):
		print(l[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = 1
	b = n
	run = True
	for i in range(n):
		if run:
			print(b, end=' ')
			b -= 1
			run = False
		else:
			print(a, end=' ')
			a += 1
			run = True
	print()


T = int(input())
for _ in range(T):
	a = int(input())
	s = ''
	if a % 2 == 0:
		for i in range(a // 2):
			s = s + ' ' + str(a) + ' ' + str(i + 1)
			a -= 1
		print(s)
	else:
		for i in range(a // 2 + 1):
			s = s + ' ' + str(a) + ' ' + str(i + 1)
			a -= 1
		print(s[1:len(s) - (len(str(a)) + 1)])


t = int(input())
for i in range(t):
	n = int(input())
	l = list(range(0, n + 1))
	p = []
	for i in range(1, int(n // 2) + 1):
		p.append(l[-1 * i])
		p.append(l[1 * i])
	if n % 2 == 0:
		for i in p:
			print(i, end=' ')
		print()
	else:
		p.append(l[-1 * (n // 2 + 1)])
		for i in p:
			print(i, end=' ')
		print()


import sys
from os import path
from math import gcd
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	seq = []
	i = n
	seq.append(i)
	while len(seq) < n:
		seq.append(0)
		seq.append(i - 1)
		i -= 1
	if n % 2 != 0:
		c = 0
		for i in range(n - 2, 0, -2):
			if i == n - 2:
				seq[i] = seq[i + 1] - 1
				c = seq[i]
			else:
				seq[i] = c - 1
				c -= 1
	else:
		seq[-2] = seq[-1]
		seq = seq[:-1]
		c = seq[-1]
		for i in range(n - 3, 0, -2):
			seq[i] = c - 1
			c -= 1
	for i in seq:
		print(i, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	l1 = []
	l2 = []
	for i in range(1, n + 1):
		l1.append(i)
	for i in range(n):
		if len(l1) == 0:
			break
		if len(l1) == 1:
			l2.append(l1[0])
			del l1[0]
		elif len(l1) % 2 == 0:
			l2.append(l1[int(len(l1) / 2) - 1])
			del l1[int(len(l1) / 2) - 1]
		elif len(l1) % 2 == 1:
			l2.append(l1[int(len(l1) / 2)])
			del l1[int(len(l1) / 2)]
	l2 = l2[::-1]
	for i in l2:
		print(i, end=' ')
	print()


T = int(input())
while T:
	n = int(input())
	if n == 1:
		print(n)
	else:
		first = n
		sec = 1
		for i in range(n):
			if i % 2 == 1:
				print(sec, end=' ')
				sec += 1
			else:
				print(first, end=' ')
				first -= 1
		print()
	T = T - 1


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	else:
		first = n
		sec = 1
		for i in range(n):
			if i % 2 == 0:
				print(first, end=' ')
				first -= 1
			else:
				print(sec, end=' ')
				sec += 1
		print()


for _ in range(int(input())):
	n = int(input())
	lst = list(range(1, n + 1))
	answer = ''
	i = 1
	for x in range(n):
		if x % 2 == 0:
			answer += str(n) + ' '
			n -= 1
		else:
			answer += str(i) + ' '
			i += 1
	print(answer)


def solve(x):
	bigger = x
	smaller = 1
	while bigger >= smaller:
		if bigger == smaller:
			print(bigger, end=' ')
			break
		print(bigger, end=' ')
		bigger -= 1
		print(smaller, end=' ')
		smaller += 1
	print()
for _ in range(int(input(''))):
	solve(*list(map(int, input().split())))


def median(arr):
	arr.sort()
	if len(arr) % 2 == 0:
		return arr[len(arr) / 2 - 1]
	else:
		return arr[len(arr) // 2]

def solve(x):
	bigger = x
	smaller = 1
	arr = []
	while bigger >= smaller:
		if bigger == smaller:
			arr.append(bigger)
			break
		arr.append(bigger)
		bigger -= 1
		arr.append(smaller)
		smaller += 1
	return arr
for _ in range(int(input(''))):
	[print(i, end=' ') for i in solve(*list(map(int, input().split())))]
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n // 2):
		l.append(n - i)
		l.append(i + 1)
	if n % 2 != 0:
		l.append(n // 2 + 1)
	print(*l)


T = int(input())
ans = []
for i in range(0, T):
	a = int(input())
	li = []
	for j in range(1, a + 1):
		li.append(j)
	ab = ''
	for j in range(0, a // 2):
		ab = ab + str(li[a - j - 1]) + ' ' + str(li[j]) + ' '
	if a % 2 == 1:
		ab += str(li[a // 2])
	print(ab)


for _ in range(int(input())):
	n = int(input())
	l1 = []
	if n == 1:
		print(1)
	else:
		if n % 2 == 0:
			for i in range(1, n // 2 + 1):
				l1.append(n - i + 1)
				l1.append(i)
		else:
			for i in range(1, n // 2 + 2):
				if i != n // 2 + 1:
					l1.append(n - i + 1)
					l1.append(i)
				else:
					l1.append(i)
		print(*l1)


for _ in range(int(input())):
	n = int(input())
	a = [i for i in range(1, n + 1)]
	(l, x, y) = ([], 1, 0)
	for i in range(1, n + 1):
		if i % 2 == 0:
			l.append(a[y])
			y += 1
		else:
			l.append(a[-x])
			x += 1
	print(*l)


t = int(input())
while t > 0:
	n = int(input())
	a = 1
	b = n
	ans = ''
	while b > 1:
		ans += str(n) + ' '
		ans += str(a) + ' '
		a += 1
		n -= 1
		b -= 2
	if b == 1:
		ans += str(n) + ' '
	print(ans)
	t -= 1


def func(a):
	l = []
	if a % 2 == 0:
		b = a // 2
		for i in range(a):
			if i % 2 == 0:
				l.append(b - (i + 1) // 2)
			else:
				l.append(b + (i + 1) // 2)
	else:
		b = a // 2 + 1
		for i in range(a):
			if i % 2 == 0:
				l.append(b + (i + 1) // 2)
			else:
				l.append(b - (i + 1) // 2)
	return reversed(l)
t = int(input())
for i in range(t):
	a = int(input())
	print(*func(a))


ans = ''
for _ in range(int(input())):
	n = int(input())
	res = ''
	i = 1
	j = n
	while i <= j:
		res += str(j) + ' '
		j -= 1
		if i > j:
			break
		res += str(i) + ' '
		i += 1
	ans += res + '\n'
print(ans)


for test in range(int(input())):
	N = int(input())
	counter = 0
	time = 0
	output = []
	for i in range(N - 1):
		if time % 2 == 0:
			output.append(N - counter)
			counter += 1
			time += 1
		else:
			output.append(counter)
			time += 1
	if N % 2 != 0:
		output.append(int(N / 2) + 1)
	else:
		output.append(N // 2)
	for i in output:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = [i for i in range(1, n + 1)]
	(s, a, b) = ([], 1, 0)
	for i in range(1, n + 1):
		if i % 2 == 1:
			s.append(l[-a])
			a += 1
		else:
			s.append(l[b])
			b += 1
	print(*s)


for _ in range(int(input())):
	n = int(input())
	x = n
	m = 1
	for i in range(n):
		if i % 2 == 0:
			print(x, end=' ')
			x -= 1
		else:
			print(m, end=' ')
			m += 1
	print()


t = int(input())
for tt in range(t):
	n = int(input())
	list1 = []
	val1 = n
	val2 = 1
	odd = True
	for i in range(n):
		if odd == True:
			list1.append(val1)
			val1 -= 1
			odd = False
		elif odd == False:
			list1.append(val2)
			val2 += 1
			odd = True
	print(' '.join([str(x) for x in list1]))


tst = int(input())
while tst > 0:
	tst = tst - 1
	n = int(input())
	flag = 0
	if n % 2 == 0:
		mean = n // 2
		flag = 1
	else:
		mean = (n + 1) // 2
		flag = 0
	a = []
	e = mean
	o = mean
	i = 0
	while i < n:
		if flag == 1:
			a.append(e + 1)
			e = e + 1
			flag = 0
		elif flag == 0:
			a.append(o - 1)
			o = o - 1
			flag = 1
		i = i + 1
	i = n - 2
	while i >= 0:
		print(a[i], end=' ')
		i -= 1
	print(mean)


T = int(input())
for i in range(T):
	N = int(input())
	x = N
	p = N
	q = 1
	while x != 0:
		if x != 1:
			print(p, end=' ')
		else:
			print(p)
		x -= 1
		p -= 1
		if q != p + 1:
			if x != 1:
				print(q, end=' ')
			else:
				print(q)
			q += 1
			x -= 1


def median(n):
	if n % 2 == 0:
		return n // 2
	else:
		return (n + 1) // 2
t = int(input())
for i in range(t):
	n = int(input())
	arr = [j for j in range(1, n + 1)]
	ans = [0] * n
	m = n
	for j in range(n - 1, -1, -1):
		k = median(m) - 1
		ans[j] = arr[k]
		arr.pop(k)
		m = m - 1
	for ele in ans:
		print(ele, end=' ')
	print()


n = int(input())
for _ in range(n):
	m = int(input())
	l = []
	for i in range(m):
		l.append(m - i)
		l.append(i + 1)
	for i in range(len(l) // 2):
		print(l[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	lst = []
	x = n
	y = 1
	for i in range(1, n + 1):
		if i % 2 != 0:
			lst.append(x)
			x = x - 1
		else:
			lst.append(y)
			y = y + 1
	for items in lst:
		print('{0}  '.format(items), end='')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	(a, b) = (n, 1)
	for j in range(n):
		if j % 2 == 0:
			l.append(a)
			a -= 1
		else:
			l.append(b)
			b += 1
	print(*l)


for _ in range(int(input())):
	n = int(input())
	p = []
	if n % 2 == 0:
		p.append(n // 2)
		p.append(n // 2 + 1)
		left = n // 2 - 1
		right = n // 2 + 2
	else:
		p.append(n // 2 + 1)
		left = n // 2
		right = n // 2 + 2
	while left > 0 and right <= n:
		p.append(left)
		p.append(right)
		left -= 1
		right += 1
	print(*p[::-1])