Chef is given an integer N. Chef wants to construct a [permutation] A = [A_{1}, A_{2}, \ldots, A_{N}] of \{1, 2, 3, \ldots, N \} that satisfies the following condition:

Let P_{i} denote the prefix of A of length i, i.e, P_{i} = [A_{1}, A_{2}, \ldots, A_{i}]. Then, for every 1 ≤ i < N, it must hold that \text{median}(P_{i}) \neq \text{median}(P_{i+1})

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

Note: The median of an array is defined as follows:
Let A be an (1-indexed) array of length N. Let B be the array obtained by sorting A. Then \text{median}(A) is defined to be B_{\lceil \frac{N}{2}\right\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 T, denoting the number of test cases.
- The first and only line of each test case contains a single integer N.

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

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

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

$1 ≤ T ≤ 30$
$2 ≤ N ≤ 1000$
- The sum of $N$ over all test cases won't exceed $1000$.

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

----- Sample Output 1 ------ 
2 1
2 1 3

----- explanation 1 ------ 
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.

Difficulty: MEDIUM
Tags: Combinatorics

Mathematics

Constructive algorithms

Starter code:

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


import math
for i in range(int(input())):
	n = int(input())
	for i in range(n):
		if i % 2 == 0:
			print((n + i) // 2 + 1, end=' ')
		else:
			print(math.ceil((n - i) / 2), end=' ')
	print()


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


v = int(input())
s = []
for vv in range(0, v):
	t = int(input())
	s.append(t)
for ccx in s:
	g = []
	for xxa in range(1, ccx + 1):
		g.append(str(xxa))
	alp = ccx
	if ccx % 2 != 0:
		alp -= 1
	while alp > 2:
		upm = alp // 2 - 1
		mmre = g[upm]
		jjk = g[alp - 1]
		g[alp - 1] = mmre
		g[upm] = jjk
		alp -= 2
	jmr = g[0]
	pnai = g[1]
	g[1] = jmr
	g[0] = pnai
	eee = ' '.join(g)
	print(eee)


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


for i in range(int(input())):
	n = int(input())
	c = 0
	s = ''
	top = n // 2 + 1
	for i in range(1, n + 1):
		c = c * -1
		top = top + c
		s = s + str(top) + ' '
		if c < 0:
			c -= 1
		else:
			c += 1
	print(s)


t = int(input())
for j in range(t):
	n = int(input())
	s = []
	for (i, j) in zip(range(n, n // 2, -1), range(1, n // 2 + 1)):
		s.append(str(i))
		s.append(str(j))
	if n % 2 != 0:
		s.append(str(n // 2 + 1))
	print(' '.join(s))


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


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


t = int(input())
while t:
	n = int(input())
	a = n // 2
	b = a + 1
	while a >= 1:
		print(b, a, end=' ')
		b += 1
		a -= 1
	if b == n:
		print(n, end=' ')
	print()
	t -= 1


q = int(input())
for i in range(q):
	w = int(input())
	e = []
	for i in range(w):
		e.append(str(w - i))
	r = ''
	if w == 1:
		print(1)
	if w == 2:
		print('2 1')
	elif w % 2 == 0:
		for i in range(int(w / 2) - 1):
			r = r + e[i] + ' '
			r = r + e[w - 1 - i] + ' '
		r = r + e[i + 1] + ' '
		r = r + e[w - 2 - i]
		print(r)
	elif w % 2 == 1:
		for i in range(int((w - 1) / 2)):
			r = r + e[i] + ' '
			r = r + e[w - 1 - i] + ' '
		r = r + e[i + 1]
		print(r)


for _ in range(int(input())):
	N = int(input())
	high = N
	low = 1
	A = []
	i = 0
	while high >= low:
		if i % 2:
			A.append(low)
			low += 1
		else:
			A.append(high)
			high -= 1
		i = not i
	print(*A)


for tc in range(int(input())):
	n = int(input())
	a1 = n // 2
	a2 = n - a1
	arr = []
	(arr1, arr2) = ([], [])
	for i in range(1, a1 + 1):
		arr1.append(i)
	for i in range(a1 + 1, n + 1):
		arr2.append(i)
	(p2, p1, ap) = (a2 - 1, 0, 0)
	for i in range(n):
		if i % 2 == 0:
			arr.append(arr2[p2])
			p2 -= 1
		else:
			arr.append(arr1[p1])
			p1 += 1
	print(*arr)


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)


for t in range(int(input())):
	n = int(input())
	re = []
	x1 = n
	x2 = 1
	for i in range(n // 2):
		re.append(x1)
		re.append(x2)
		x1 -= 1
		x2 += 1
	if n % 2 == 1:
		re.append(x1)
	print(*re)


for _ in range(int(input())):
	n = int(input())
	res = []
	x1 = n
	x2 = 1
	for i in range(n // 2):
		res.append(x1)
		res.append(x2)
		x1 -= 1
		x2 += 1
	if n % 2 == 1:
		res.append(x1)
	print(*res)


for _ in range(int(input())):
	n = int(input())
	l = [0] * n
	k = 1
	for i in range(1, n, 2):
		l[i] = k
		k += 1
	for i in range(0, n, 2):
		l[i] = k
		k += 1
	print(*l)


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


for i in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		middle = n // 2
		a = []
		for j in range(1, middle + 1):
			a.append(n - middle + j)
			a.append(n - middle - j + 1)
	else:
		middle = n // 2 + 1
		a = [middle]
		for j in range(1, middle):
			a.append(middle - j)
			a.append(middle + j)
	print(' '.join((str(eng) for eng in a)))


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		mid = n // 2
		a = []
		for j in range(1, mid + 1):
			a.append(n - mid + j)
			a.append(n - mid - j + 1)
	else:
		mid = n // 2 + 1
		a = [mid]
		for j in range(1, mid):
			a.append(mid - j)
			a.append(mid + j)
	print(' '.join((str(e) for e in a)))


t = int(input())
for _ in range(t):
	n = int(input())
	s = str(n // 2 + 1)
	for x in range(1, (n + 1) // 2):
		s = s + ' ' + str(n // 2 + 1 - x) + ' ' + str(n // 2 + 1 + x)
	if n % 2 == 0:
		s = s + ' ' + str(1)
	print(s)


case = int(input())
for _ in range(case):
	n = int(input())
	p = n
	q = 1
	for i in range(n // 2):
		print(p, q, end=' ')
		p -= 1
		q += 1
	if n & 1 == 1:
		print(q, end='')
	print()


for i in range(int(input())):
	n = int(input())
	h = n // 2 + 1
	flag = False
	for i in range(0, n):
		if not flag:
			h = h + i
		if flag:
			h = h - i
		flag = not flag
		print(h, end=' ')
	print()


import statistics
for i in range(int(input())):
	n = int(input())
	k = n // 2 + 1
	flag = False
	for i in range(0, n):
		if not flag:
			k = k + i
		if flag:
			k = k - i
		flag = not flag
		print(k, end=' ')
	print()


for _ in range(int(input())):
	N = int(input())
	A = []
	a = 0
	for i in range(N):
		A.append(i + 1)
	while len(A) > 0:
		if a % 2 == 0:
			print(max(A), end=' ')
			A.remove(max(A))
		else:
			print(min(A), end=' ')
			A.remove(min(A))
		a += 1
	print()


for _ in range(int(input())):
	n = int(input())
	l = [i for i in range(1, n + 1)]
	arr1 = l[n // 2:][::-1]
	arr2 = l[:n // 2][::-1]
	if n == 1:
		print(1)
		continue
	if n % 2 == 0:
		for i in range(n // 2):
			print(arr1[i], end=' ')
			print(arr2[i], end=' ')
		print('')
	else:
		for i in range(n // 2):
			print(arr1[i], end=' ')
			print(arr2[i], end=' ')
		print(arr1[i + 1])


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


t = int(input())
for x in range(t):
	n = int(input())
	A = []
	for i in range(1, n // 2 + 1):
		A.append(n - i + 1)
		A.append(i)
	print(*A + [n - i]) if n & 1 == 1 else print(*A)


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


for i in range(int(input())):
	N = int(input())
	lis = [None] * N
	for x in range(N // 2):
		lis[2 * x] = N - x
		lis[2 * x + 1] = x + 1
	if N & 1:
		lis[N - 1] = N // 2 + 1
	print(*lis)


for _ in range(int(input())):
	n = int(input())
	elem = n // 2 + 1
	flag = False
	ans = ''
	for i in range(n):
		if flag:
			elem -= i
		if not flag:
			elem += i
		flag = not flag
		ans += str(elem) + ' '
	print(ans)


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


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


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


t = int(input())
while t > 0:
	n = int(input())
	i = n
	j = 1
	while i > n // 2 and j <= n // 2:
		print(i, end=' ')
		print(j, end=' ')
		i -= 1
		j += 1
	if n % 2 != 0:
		print(i, end=' ')
	print()
	t -= 1


v = input()
for m in range(0, int(v)):
	k = int(input())
	c = []
	(l, h) = (1, k)
	while l <= h:
		c.append(str(h))
		h -= 1
		if h >= l:
			c.append(str(l))
			l += 1
	print(' '.join(c))


t = input()
for c in range(0, int(t)):
	N = int(input())
	P = []
	(l, h) = (1, N)
	while l <= h:
		P.append(str(h))
		h -= 1
		if h >= l:
			P.append(str(l))
			l += 1
	print(' '.join(P))


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	N = get_int()
	P = []
	(l, h) = (1, N)
	while l <= h:
		P.append(str(h))
		h -= 1
		if h >= l:
			P.append(str(l))
			l += 1
	print(' '.join(P))


for _ in range(int(input())):
	listt = []
	for i in range(1, int(input()) + 1):
		listt.append(str(i))
	if len(listt) > 2:
		s = ''
		s += listt[-2] + ' '
		listt.pop(-2)
		i = 0
		while i < len(listt) // 2:
			s += listt[i] + ' '
			s += listt[-(i + 1)] + ' '
			i += 1
		if len(listt) % 2 != 0:
			s += listt[len(listt) // 2]
		print(s)
	elif len(listt) == 2:
		print('2 1')
	else:
		print('1')


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = []
	answer = []
	for i in range(1, n + 1):
		arr.append(i)
	for i in range(0, n):
		if i % 2 == 0:
			answer.append(arr[len(arr) - 1])
			arr.pop()
		else:
			answer.append(arr[0])
			arr.remove(arr[0])
	print(*answer)


t = int(input())
while t:
	t -= 1
	li = []
	n = int(input())
	(i, j) = (1, n)
	for _ in range(n // 2):
		li.append(j)
		j -= 1
		li.append(i)
		i += 1
		if i == j:
			li.append(i)
	for _ in li:
		print(_, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	lis = []
	s = 1
	e = n
	j = 0
	while len(lis) != n:
		if len(lis) != n:
			lis.append(e)
			e -= 1
		if len(lis) != n:
			lis.append(s)
			s += 1
	for i in lis:
		print(i, end=' ')
	print()


import sys

def input():
	return sys.stdin.readline().strip()

def print(n):
	return sys.stdout.write(str(n) + '\n')
for _ in range(int(input())):
	n = int(input())
	a = ''
	a += str(n) + ' '
	for i in range(1, n // 2 + 1):
		if i == n - i:
			a += str(i) + ' '
		else:
			a += str(i) + ' ' + str(n - i) + ' '
	print(a)


def median_check(a):

	def median(a):
		return a[(len(a) + 1) // 2 - 1]
	done = []
	for i in range(1, len(a) + 1):
		cur = sorted(a[:i])
		if median(cur) in done:
			print(done)
			return False
		else:
			done.append(median(cur))
	return True
for t in range(int(input())):
	n = int(input())
	n_array = range(1, n + 1)
	a = []
	end = False
	(top, bot) = (n - 1, 0)
	while end == False:
		if top == bot:
			cur = [n_array[top]]
			end = True
		else:
			cur = [n_array[top], n_array[bot]]
			if top == bot + 1:
				end = True
		top -= 1
		bot += 1
		a += cur
	print(*a)


for _ in range(int(input())):
	n = int(input())
	ans = ''
	ans += str(n) + ' '
	for i in range(1, n // 2 + 1):
		if i == n - i:
			ans += str(i) + ' '
		else:
			ans += str(i) + ' ' + str(n - i) + ' '
	print(ans)


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


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


import math

def med_diff(N):
	if N == 2:
		return [2, 1]
	median = N // 2 + 1
	array = []
	array.append(median)
	temp = median
	temp_1 = median
	for i in range(1, N):
		if i % 2 == 0:
			array.append(temp + 1)
			temp += 1
		else:
			array.append(temp_1 - 1)
			temp_1 -= 1
	return array
t = input()
for i in range(int(t)):
	n = input()
	array = med_diff(int(n))
	print(*array)


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


for _ in range(int(input())):
	n = int(input())
	m = n
	for i in range(n):
		if not i & 1:
			print(m, end=' ')
			m -= 1
		else:
			print(i // 2 + 1, end=' ')
	print()


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


for _ in range(int(input())):
	n = int(input())
	a = []
	(L, R) = (1, 2)
	for i in range(n):
		if i % 2 == 1:
			a.append(L)
			L -= 1
		else:
			a.append(R)
			R += 1
	m = min(a)
	print(' '.join((str(x - m + 1) for x in a)))