You are given an integer N.

Find a permutation P = [P_{1}, P_{2}, \ldots, P_{N}] of the integers \{1, 2, \ldots, N\} such that sum of averages of all consecutive triplets is minimized, i.e. 

\sum_{i=1}^{N-2} \frac{P_{i} + P_{i+1} + P_{i+2}}{3}

is minimized.

If multiple permutations are possible, print any of them.

------ 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 an integer N, the size of the permutation.

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

For each test case, output on a new line a permutation which satisfies the above conditions.

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

$1 ≤ T ≤ 1000$
$3 ≤ N ≤ 10^{5}$
- The sum of $N$ over all test cases won't exceed $3\cdot 10^{5}$.

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

----- Sample Output 1 ------ 
3 2 1 4
3 2 1
----- explanation 1 ------ 
Test case $1$: The sum is $\frac{P_{1} + P_{2} + P_{3}}{3} + \frac{P_{2} + P_{3} + P_{4}}{3} = \frac{3 + 2 + 1}{3} + \frac{2 + 1 + 4}{3} = 6/3 + 7/3 = 4.333\ldots$ Among all possible permutations of $\{1, 2, 3, 4\}$, this is one of the permutations which provides the minimum result.

Test case $2$: The sum is $\frac{3+2+1}{3} = 6/3 = 2$. Every permutation of size $3$ will have this value, hence it is the minimum possible.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	if N == 3:
		print('3 2 1')
	elif N == 4:
		print('3 2 1 4')
	else:
		arr = [0] * N
		for i in range(2, N - 2):
			arr[i] = i - 1
		arr[0] = N
		arr[-1] = N - 1
		arr[1] = N - 2
		arr[-2] = N - 3
		print(' '.join((str(x) for x in arr)))


for i in range(int(input())):
	n = int(input())
	array = []
	for i in range(n):
		array.append(i + 1)
	(array[-2], array[-3], array[0]) = (array[-3], array[0], array[-2])
	if len(array) >= 5:
		(array[1], array[-4]) = (array[-4], array[1])
	print(*array)


t = int(input())
while t != 0:
	array = []
	arraylen = int(input())
	for i in range(arraylen):
		array.append(i + 1)
	(array[-2], array[-3], array[0]) = (array[-3], array[0], array[-2])
	if arraylen >= 5:
		(array[1], array[-4]) = (array[-4], array[1])
	theperm = list(map(str, array))
	print(' '.join(theperm))
	t -= 1


from itertools import permutations
for test in range(int(input())):
	a = int(input())
	evens = []
	odds = []
	for y in [x + 1 for x in range(a)]:
		if y % 2 == 0:
			evens += [y]
		else:
			odds += [y]
	evens.reverse()
	print(' '.join([str(x) for x in evens]) + ' ' + ' '.join([str(x) for x in odds]))


t = int(input())
i = 0
while i < t:
	l = []
	k = []
	n = int(input())
	if n > 3:
		for j in range(1, n + 1):
			l.append(j)
		p = l[n - 1]
		q = l[n - 2]
		r = l[n - 3]
		s = l[n - 4]
		o = l[0:n - 4]
		k.append(p)
		k.append(r)
		for j in o:
			k.append(j)
		k.append(s)
		k.append(q)
		for j in k:
			print(j, end=' ')
		print()
	else:
		print('3 2 1')
	i += 1


for _ in range(int(input())):
	k = int(input())
	if k >= 3:
		print(k - 1, k - 2, end=' ')
		for i in range(1, k - 2):
			print(i, end=' ')
		print(k)
	elif k == 2:
		print(1, 2)
	elif k == 1:
		print(1)


for _ in range(int(input())):
	n = int(input())
	if n > 3:
		print(n - 1, n - 2, end=' ')
		for i in range(1, n - 2):
			print(i, end=' ')
		print(n)
	elif n == 3:
		print(3, 2, 1)
	elif n == 2:
		print(1, 2)
	else:
		print(1)


t = int(input())
while t > 0:
	n = int(input())
	if n > 3:
		print(n - 1, end=' ')
		print(n - 2, end=' ')
		for i in range(1, n - 2):
			print(i, end=' ')
		print(n)
	else:
		print(1, 2, 3)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	x = 1
	prem = [0] * n
	if n == 3:
		print('1 2 3')
	else:
		prem[0] = n - 1
		prem[n - 2] = n - 3
		prem[n - 1] = n
		prem[1] = n - 2
		for i in range(n):
			if prem[i] == 0:
				prem[i] = x
				x += 1
		print(' '.join((str(p) for p in prem)))


T = int(input())
for i in range(T):
	N = int(input())
	if N == 3:
		print('1 2 3')
		continue
	l = [str(j) for j in range(1, N + 1)]
	l = [l[-2], l[-4]] + l[:-4] + [l[-3], l[-1]]
	print(' '.join(l))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(range(1, n + 1))
	nl = []
	for i in l[::2]:
		nl.append(i)
	nl = list(reversed(nl))
	for j in l[1::2]:
		nl.append(j)
	print(' '.join([str(k) for k in nl]))


T = int(input())
for i in range(T):
	N = int(input())
	L = [N - 1, N - 2] + [j for j in range(1, N - 3)] + [N - 3, N]
	for j in L:
		if j > 0:
			print(j, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	ls = list(range(1, n + 1))
	ls.insert(0, ls.pop())
	ls.insert(1, ls.pop(-2))
	for i in ls:
		print(i, end=' ')
	print()


t = int(input())
while t:
	t -= 1
	n = int(input())
	if n - 2 > 0:
		print(n - 1, n - 2, end=' ')
		for k in range(1, n - 2):
			print(k, end=' ')
		print(n)
	elif n == 2:
		print(1, 2)
	else:
		print(1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l1 = []
	for k in range(1, n + 1):
		l1.append(k)
	i = len(l1) - 3
	while i != len(l1) - 1:
		k = l1[i]
		l1.remove(l1[i])
		l1.insert(0, k)
		i += 1
	for k in l1:
		print(k, end=' ')
	print('\n', end='')


trials = int(input())
for i in range(trials):
	size = int(input())
	if size == 3:
		print('3 2 1')
		continue
	elif size == 4:
		print('3 2 1 4')
		continue
	first_two = ' '.join((str(x) for x in [size, size - 2]))
	middle = ' ' + ' '.join((str(x) for x in range(1, size - 3)))
	last_two = ' ' + ' '.join((str(x) for x in [size - 3, size - 1]))
	print(first_two + middle + last_two)


for i in range(0, int(input())):
	n = int(input())
	l = [n, n - 2]
	for j in range(1, n - 3):
		l.append(j)
	l.append(n - 3)
	l.append(n - 1)
	for h in range(0, len(l)):
		if l[h] <= 0:
			continue
		elif h == len(l) - 1:
			print(l[h])
		else:
			print(l[h], end=' ')


t = int(input())
for i in range(t):
	n = int(input())
	if n == 3:
		print('1 2 3')
	elif n == 4:
		print('3 2 1 4')
	else:
		for j in range(n - 1):
			if j == 0:
				print(n - 1, end=' ')
			elif j == 1:
				print(n - 2, end=' ')
			else:
				print(j - 1, end=' ')
		print(n)


i = int(input())
lisk = []
for _ in range(i):
	k = int(input())
	finl = []
	pp = k
	if k % 2 == 1:
		for kk in range((k + 1) // 2):
			finl.append(pp)
			pp = pp - 2
	else:
		pp = pp - 1
		for kk in range(k // 2):
			finl.append(pp)
			pp = pp - 2
	c = 2
	for kk in range(k // 2):
		finl.append(c)
		c = c + 2
	tt = str(finl[0])
	for ele in range(1, len(finl)):
		tt = tt + ' ' + str(finl[ele])
	lisk.append(tt)
for ele in lisk:
	print(ele)


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


x = int(input())
m = []
for it in range(0, x):
	l = int(input())
	m.append(l)
for bb in m:
	lt = []
	for inn in range(1, bb + 1):
		lt.append(str(inn))
	if bb == 3:
		mm = ' '.join(lt)
		print(mm)
	else:
		jjr = lt[-1]
		lt.pop(-1)
		lt.insert(0, jjr)
		iit = lt[-2]
		lt.pop(-2)
		lt.insert(1, iit)
		oo = ' '.join(lt)
		print(oo)


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	a.append(n - 1)
	a.append(n - 2)
	for j in range(n - 3):
		a.append(j + 1)
	a.append(n)
	for j in range(n):
		print(a[j], end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	(a, b, c, d) = (n, n - 1, n - 2, n - 3)
	if n == 3:
		print(1, 2, 3)
	else:
		l = []
		l.append(a)
		l.append(d)
		for i in range(1, n - 3):
			l.append(i)
		l.append(c)
		l.append(b)
		for i in l:
			print(i, end=' ')
	print('')


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 3:
		print('3 2 1')
	else:
		a = [n] + [n - 2] + [i for i in range(1, n - 3)] + [n - 3] + [n - 1]
		string = ''
		for i in a:
			string += str(i) + ' '
		print(string)


for i in range(int(input())):
	u = int(input())
	k = [2, 1]
	for j in range(3, u + 1):
		if j % 2 == 0:
			k.insert(0, j)
		else:
			k.append(j)
	print(*k)


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


t = int(input())
for i in range(t):
	n = int(input())
	l = list()
	if n > 4:
		l.extend([n, n - 2, n - 3, n - 1])
		for k in range(4, n):
			l.insert(k - 2, n - k)
		for p in l:
			print(p, end=' ')
	elif n == 4:
		print('3 2 1 4')
	elif n == 3:
		print('3 2 1')


t = int(input())
for k in range(t):
	n = int(input())
	a = [i for i in range(1, n + 1)]
	if n == 3:
		print(1, 2, 3)
		continue
	print(n, n - 2, end=' ')
	for i in range(1, n - 3):
		print(i, ' ')
	print(n - 3, n - 1, end=' ')
	print()


tc = int(input())
for i in range(tc):
	n = int(input())
	arre = []
	arro = []
	for j in range(n, 0, -1):
		if j % 2 == 0:
			arre.append(j)
		else:
			arro.append(j)
	while len(arre) != 0:
		arro.append(arre.pop())
	ans = ''
	for i in arro:
		ans += str(i) + ' '
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	n1 = n - 1
	res = []
	if n % 2 == 0:
		for i in range(n1, 0, -2):
			res.append(i)
		for i in range(2, n + 1, 2):
			res.append(i)
	else:
		for i in range(n1, 1, -2):
			res.append(i)
		for i in range(1, n + 1, 2):
			res.append(i)
	res = [str(x) for x in res]
	s = ' '.join(res)
	print(s)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = [0] * n
	if n == 3:
		print(1, 2, 3)
	else:
		a[0] = n
		a[n - 1] = n - 1
		a[n - 2] = n - 2
		a[1] = n - 3
		x = 1
		for i in range(n):
			if a[i] == 0:
				a[i] = x
				x += 1
		for i in a:
			print(i, end=' ')
	print()


from math import *
for i in range(int(input())):
	n = int(input())
	p = []
	p.append(n - 1)
	p.append(n - 2)
	if n > 3:
		for i in range(1, n - 3):
			p.append(i)
		p.append(n - 3)
	p.append(n)
	print(*p)


fuck = int(input())
while fuck > 0:
	a = int(input())
	i = 1
	print(a, end=' ')
	print(a - 2, end=' ')
	while i < a - 3:
		print(i, end=' ')
		i += 1
	if a > 3:
		print(a - 3, end=' ')
	print(a - 1, end=' ')
	print('\n', end='')
	fuck -= 1


for i in range(int(input())):
	n = int(input())
	print(n - 1, n - 2, end=' ')
	for i in range(1, n - 3):
		print(i, end=' ')
	if n > 3:
		print(n - 3, end=' ')
	print(n)


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


for _ in range(int(input())):
	n = int(input())
	if n > 3:
		s = []
		s = [i for i in range(1, n + 1)]
		s.sort(reverse=True)
		q1 = []
		q2 = []
		ans = []
		q1.append(s[0])
		del s[0]
		q2.append(s[0])
		del s[0]
		q1.append(s[0])
		del s[0]
		q2.append(s[0])
		del s[0]
		q2.sort()
		ans = q1 + s + q2
		print(*ans)
	else:
		s = [i for i in range(1, n + 1)]
		print(*s)


for _ in range(int(input())):
	n = int(input())
	res = [0] * n
	(fp, lp) = (0, n - 1)
	flag = True
	for i in range(n, 0, -1):
		if flag:
			res[fp] = i
			fp += 1
		else:
			res[lp] = i
			lp -= 1
		flag = not flag
	print(*res)


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


for tc in range(int(input())):
	n = int(input())
	if n == 3:
		arr = [1, 2, 3]
		print(*arr)
	else:
		(s1, s2, e1, e2) = (n - 1, n - 3, n, n - 2)
		arr = [s1, s2]
		for i in range(1, n - 3):
			arr.append(i)
		arr.append(e2)
		arr.append(e1)
		print(*arr)


for _ in range(int(input())):
	N = int(input())
	if N == 3:
		print('1 2 3')
	else:
		print(N, N - 2, end=' ')
		for k in range(2, N - 2):
			print(k - 1, end=' ')
		print(N - 3, N - 1)


for _ in range(int(input())):
	N = int(input())
	permutation = [0] * N
	if N == 3:
		permutation = [1, 2, 3]
	else:
		permutation[0] = N
		permutation[1] = N - 2
		for k in range(2, N - 1):
			permutation[k] = k - 1
		permutation[N - 2] = N - 3
		permutation[N - 1] = N - 1
	print(' '.join(map(str, permutation)))


for t in range(int(input())):
	n = int(input())
	l = [i + 1 for i in range(n)]
	for i in range(2):
		l.insert(i, l[n - i - 1])
		l.pop(n - i)
	for item in l:
		print(item, end=' ')
	print()


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


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


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


for i in range(int(input())):
	n = int(input())
	a = []
	b = []
	for i in range(1, n + 1):
		if i % 2 == 0:
			a.append(i)
		else:
			b.append(i)
	a.sort(reverse=True)
	print(*a + b)


t = int(input())
while t > 0:
	n = int(input())
	st = '1'
	for i in range(2, n + 1, 1):
		if i % 2 != 0:
			st = st + ' ' + str(i)
		else:
			st = str(i) + ' ' + st
	print(st)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	if n == 3:
		l = [3, 1, 2]
	elif n == 4:
		l = [4, 2, 1, 3]
	else:
		l = [a + 1 for a in range(n - 4)]
		l.insert(0, n)
		l.insert(1, n - 2)
		l.insert(n - 1, n - 1)
		l.insert(n - 2, n - 3)
	print(*l)


for _ in range(int(input())):
	n = int(input())
	array2 = []
	array1 = []
	for i in range(1, n + 1):
		if i % 2 == 0:
			array1.append(i)
		else:
			array2.append(i)
	array1.sort(reverse=True)
	array = array1 + array2
	print(*array)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(i + 1)
	(l[-2], l[-3], l[0]) = (l[-3], l[0], l[-2])
	if n >= 5:
		(l[1], l[-4]) = (l[-4], l[1])
	result = list(map(str, l))
	print(' '.join(result))


for t in range(int(input())):
	x = int(input())
	l = []
	i = x
	while i > 0:
		if i % 2 == 0:
			l.append(i)
			i = i - 2
		else:
			if i > 1:
				l.append(i - 1)
			i = i - 2
	i = 1
	while i <= x:
		l.append(i)
		i = i + 2
	print(' '.join((str(x) for x in l)))


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


for t in range(int(input())):
	n = int(input())
	arre = [2, 1, 3]
	arro = [3, 1, 2]
	if n & 1 == 0:
		er = (n - 3) // 2
		el = (n - 2) // 2
		for i in range(el):
			arre.insert(0, arre[0] + 2)
		for j in range(er):
			arre.append(arre[len(arre) - 1] + 2)
		print(*arre, end=' ')
	else:
		er = (n - 3) // 2
		for i in range(er):
			arro.insert(0, arro[0] + 2)
		for j in range(er):
			arro.append(arro[len(arro) - 1] + 2)
		print(*arro, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	available_integers = range(1, n + 1)
	new_array = [1] * n
	right_pointer = -1
	left_pointer = 0
	pointer_osc_left = True
	for i in reversed(available_integers):
		if pointer_osc_left:
			new_array[left_pointer] = i
			left_pointer += 1
			pointer_osc_left = False
		else:
			new_array[right_pointer] = i
			right_pointer -= 1
			pointer_osc_left = True
	print(*new_array, end=' ' + '\n')


tc = int(input())
for _ in range(tc):
	n = int(input())
	if n > 3:
		num = []
		for i in range(n):
			num.append(i + 1)
		out = [num[n - 1], num[n - 3]]
		num.pop(n - 1)
		num.pop(n - 3)
		for i in num:
			out.append(i)
		print(*out)
	else:
		print(1, 2, 3)


tc = int(input())
for t in range(tc):
	n = int(input())
	if n == 3:
		for i in range(n):
			print(i + 1, end=' ')
	else:
		print(n, n - 2, end=' ')
		for i in range(n - 4):
			print(i + 1, end=' ')
		print(n - 3, n - 1)


for _ in range(int(input())):
	n = int(input())
	l = [x for x in range(1, n + 1)]
	if n > 3:
		a = l.pop(-4)
		b = l.pop(-2)
		l.insert(0, a)
		l.insert(0, b)
		print(*l)
	else:
		print(*l)


def solve_test_case(N):
	L = list(range(1, N + 1))
	m = len(L) - 1
	(L[0], L[1], L[m - 3], L[m - 2], L[m - 1]) = (L[m - 1], L[m - 3], L[1], L[0], L[m - 2])
	if N == 3:
		L = [1, 2, 3]
	if N == 4:
		L = [3, 1, 2, 4]
	print_list(L)

def print_list(L):
	print(' '.join(map(str, L)))
for _ in range(int(input())):
	solve_test_case(int(input()))