You are given an integer $n$. You have to construct a permutation of size $n$.

A permutation is an array where each integer from $1$ to $s$ (where $s$ is the size of permutation) occurs exactly once. For example, $[2, 1, 4, 3]$ is a permutation of size $4$; $[1, 2, 4, 5, 3]$ is a permutation of size $5$; $[1, 4, 3]$ is not a permutation (the integer $2$ is absent), $[2, 1, 3, 1]$ is not a permutation (the integer $1$ appears twice).

A subsegment of a permutation is a contiguous subsequence of that permutation. For example, the permutation $[2, 1, 4, 3]$ has $10$ subsegments: $[2]$, $[2, 1]$, $[2, 1, 4]$, $[2, 1, 4, 3]$, $[1]$, $[1, 4]$, $[1, 4, 3]$, $[4]$, $[4, 3]$ and $[3]$.

The value of the permutation is the number of its subsegments which are also permutations. For example, the value of $[2, 1, 4, 3]$ is $3$ since the subsegments $[2, 1]$, $[1]$ and $[2, 1, 4, 3]$ are permutations.

You have to construct a permutation of size $n$ with minimum possible value among all permutations of size $n$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 48$) — the number of test cases.

Then, $t$ lines follow. The $i$-th of them contains one integer $n$ ($3 \le n \le 50$) representing the $i$-th test case.


-----Output-----

For each test case, print $n$ integers — the permutation of size $n$ with minimum possible value. If there are multiple such permutations, print any of them.


-----Examples-----

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


-----Note-----

In the first example, the permutation $[1, 4, 3, 5, 2]$ is one of the possible answers; its value is $2$.

In the second example, the permutation $[4, 1, 6, 2, 5, 3]$ is one of the possible answers; its value is $2$.

Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
x = int(input())

def do(has):
	return ' '.join(map(str, [1] + list(range(2, a + 1))[::-1]))
for _ in range(x):
	a = int(input())
	print(do(a))


for _ in range(int(input())):
	n = int(input())
	l = [1]
	l1 = [j for j in range(2, n + 1)]
	l1.reverse()
	print(*l + l1)


for _ in range(int(input())):
	n = int(input())
	lst = [1]
	lst.extend(range(3, n + 1))
	lst.append(2)
	print(*lst)


def fxn(n):
	ans = [0] * n
	for i in range(1, n - 1):
		ans[i] = i + 2
	ans[0] = 1
	ans[-1] = 2
	string = ''
	for i in range(len(ans)):
		string += str(ans[i])
		string += ' '
	return string
n = int(input())
for i in range(n):
	a = int(input())
	print(fxn(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [i for i in range(1, n + 1)]
	for i in range(1, n - 1):
		a[i] = i + 2
	a[n - 1] = 2
	print(' '.join(list(map(str, a))))


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


n = int(input())
while n:
	a = int(input())
	l = []
	even = []
	odd = []
	for i in range(1, a + 1):
		l.append(i)
	i = 0
	j = len(l) - 1
	x = []
	while i < j:
		x.append(l[i])
		x.append(l[j])
		i += 1
		j -= 1
	if len(l) % 2 == 1:
		x.append(l[len(l) // 2])
	for i in x:
		print(i, end=' ')
	print('')
	n -= 1


import math

def sol(n):
	s = '1 '
	for i in reversed(range(2, n + 1)):
		s += str(i)
		s += ' '
	print(s[:-1])
T = int(input())
for test_case in range(1, T + 1):
	m = int(input())
	s = sol(m)


T = int(input())
for i in range(T):
	n = int(input())
	list1 = []
	list1.append(1)
	list1.append(3)
	list1.append(2)
	if n == 3:
		print(' '.join(map(str, list1)))
	else:
		list1.remove(2)
		for i in range(4, n + 1):
			list1.append(i)
		list1.append(2)
		print(' '.join(map(str, list1)))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = [1]
	for i in range(3, n + 1):
		l.append(i)
	l.append(2)
	print(*l)


t = int(input())
for _ in range(t):
	n = int(input())
	print(' '.join(map(str, [1] + list(range(n, 1, -1)))))


for _ in range(int(input())):
	n = int(input())
	print(*[1, n] + list(range(2, n)))


for i in range(int(input())):
	a = int(input())
	b = [i for i in range(2, a + 1)]
	print(*b + [1])


t = int(input())
for i in range(t):
	n = int(input())
	answere = [0] * n
	counter = 1
	pointer = 0
	while counter <= n:
		answere[pointer] = counter
		counter += 1
		pointer = n - pointer
		if counter % 2 == 0:
			pointer -= 1
	print(*answere, end=' ')
	print('')


import math

def solve():
	n = int(input())
	res = '1'
	for i in range(n, 1, -1):
		res += ' ' + str(i)
	print(res)
t = int(input())
for _ in range(t):
	solve()


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


for i in range(int(input())):
	n1 = int(input())
	l = []
	l.append(1)
	for i in range(n1, 2, -1):
		l.append(i)
	l.append(2)
	print(*l)


t = int(input())
for i1 in range(t):
	n = int(input())
	l = [str(i) for i in range(1, n + 1)]
	(l[1], l[-1]) = (l[-1], l[1])
	print(' '.join(l))


for _ in range(int(input())):
	n = int(input())
	print(1, *[int(x) for x in range(3, n + 1)], 2)


t = int(input())
for _ in range(t):
	i = int(input())
	a = '1'
	for x in range(i - 1):
		a = a + ' ' + str(i)
		i = i - 1
	print(a)


for sv in [*open(0)][1:]:
	print(1, *range(3, int(sv) + 1), 2)


t = int(input())
if t < 1 or t > 48:
	quit()
for i in range(t):
	n = int(input())
	if 3 <= n <= 50:
		num_list = [i + 1 for i in range(n)]
		for j in range(n - 2):
			(num_list[j + 1], num_list[j + 2]) = (num_list[j + 2], num_list[j + 1])
		for k in range(n):
			print(num_list[k], end=' ')
		if i < t:
			print()
	else:
		quit()


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


for n in [*open(0)][1:]:
	print(1, *range(3, int(n) + 1), 2)


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


for _ in range(int(input())):
	l = []
	n = int(input())
	l.append(1)
	for i in range(n, 1, -1):
		l.append(i)
	print(*l)


n = int(input())
for i in range(n):
	t = int(input())
	print(1, end=' ')
	for j in range(3, t + 1):
		print(j, end=' ')
	print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = [1, n]
	ans += list(range(2, n))
	print(' '.join([str(_) for _ in ans]))


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


import math
t = int(input())
for _ in range(t):
	n = int(input())
	print(1, *range(n, 1, -1))


for _ in range(int(input())):
	n = int(input())
	arr = []
	a = 1
	b = n
	while len(arr) < n:
		arr.append(a)
		a += 1
		if len(arr) < n:
			arr.append(b)
			b -= 1
	print(*arr)


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]
t = ni()
for case in range(t):
	n = ni()
	out = [1]
	out.append(n)
	for i in range(2, n):
		out.append(i)
	print(' '.join(map(str, out)))


for _ in range(int(input())):
	n = int(input())
	a = [i for i in range(n, 0, -1)]
	a.insert(0, 1)
	a.pop()
	print(*a)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	for i in range(1, n + 1, 2):
		a.append(i)
	for i in range(2, n + 1, 2):
		b.append(i)
	b.reverse()
	a = a + b
	print(*a)


for _ in range(int(input())):
	n = int(input())
	l = []
	l.append(1)
	for i in range(3, n + 1):
		l.append(i)
	l.append(2)
	print(*(x for x in l))


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	print(1, end=' ')
	for i in range(n, 1, -1):
		print(i, end=' ')
	print()
(tt,) = inp_arr()
for t in range(tt):
	solve()


t = eval(input())
for i in range(t):
	n = eval(input())
	a = [i for i in range(1, n + 1)]
	(a[1], a[n - 1]) = (a[n - 1], a[1])
	print(*a)


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'er9fj48gh48gh4' == 14194665565:
		print('Tanmay')
	ans = '1'
	for i in range(n, 1, -1):
		ans += ' ' + str(i)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	res = [1] + list(range(n, 1, -1))
	print(*res)


import math
for jj in range(int(input())):
	n = int(input())
	ans = list(range(2, n + 1)) + [1]
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	print(1, *range(n, 1, -1))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	return [1] + [i for i in range(2, n + 1)][::-1]
for _ in range(int(input())):
	print(*solve())


n = int(input())
for i in range(n):
	b = int(input())
	ls = ['1']
	for j in range(3, b + 1):
		ls.append(str(j))
	ls.append('2')
	print(' '.join(ls))


for _ in range(int(input())):
	n = int(input())
	print(1, end=' ')
	for i in range(n, 1, -1):
		print(i, end=' ')
	print()


import math
n = int(input())
for i in range(n):
	m = int(input())
	print(1, end=' ')
	for j in range(m, 2, -1):
		print(j, end=' ')
	print(2)


for _ in range(int(input())):
	a = int(input())
	r = reversed(list(range(2, a + 1)))
	ans = [1]
	ans.extend(r)
	print(*ans)


from math import ceil
import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = []
	i = int(1)
	while i <= n:
		a.append(i)
		i += 2
	if n % 2 == 1:
		i -= 3
		m = 1
	else:
		i -= 1
	while i > 0:
		a.append(i)
		i -= 2
	for i in range(0, len(a)):
		print(a[i], end=' ')
	print()


for a in range(int(input())):
	n = int(input())
	print(1, n, *list(range(2, n)))


import math

def main():
	t = 1
	t = int(input())
	for i in range(t):
		n = int(input())
		print(1, end=' ')
		for j in range(3, n + 1):
			print(j, end=' ')
		print(2)
main()


t = int(input())
for x in range(t):
	n = int(input())
	l = [str(i) for i in range(1, n + 1) if i % 2 == 1] + [str(i) for i in range(1, n + 1) if i % 2 == 0][::-1]
	print(' '.join(l))


k = int(input())
for i in range(k):
	n = int(input())
	arr = []
	for i in range(2, n + 1):
		arr.append(i)
	arr.append(1)
	for i in range(n):
		print(arr[i], end=' ')
	print()


test = int(input())
for t in range(test):
	n = int(input())
	A = []
	A.append(1)
	for i in range(n, 1, -1):
		A.append(i)
	print(*A)


T = int(input())
for _ in range(T):
	n = int(input())
	res = [1] + [x for x in range(n, 1, -1)]
	print(*res)


def main():
	t = int(input())
	for _ in range(t):
		k = int(input())
		arr = [0 for i in range(k)]
		arr[0] = 1
		arr[-1] = 2
		for i in range(1, k - 1):
			arr[i] = i + 2
		for i in arr:
			print(i, end=' ')
		print()
main()


for i in range(int(input())):
	n = int(input())
	for i in range(2, n + 1):
		print(i, end=' ')
	print(1)


t = int(input())
for t1 in range(t):
	n = int(input())
	print(1, end=' ')
	for i in range(n, 1, -1):
		print(i, end=' ')
	print()


def exe():
	ans = [1]
	for i in range(n, 1, -1):
		ans.append(i)
	return ans
for i in range(int(input())):
	n = int(input())
	print(*exe())


for test in range(int(input())):
	n = int(input())
	print('1', end=' ')
	for i in range(3, n + 1):
		print(i, end=' ')
	print('2 ')


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


for _ in range(int(input())):
	n = int(input())
	s = '1'
	for i in range(n, 1, -1):
		s += ' ' + str(i)
	print(s)


try:
	for _ in range(int(input())):
		n = int(input())
		print(1, n, end=' ')
		print(*list(range(2, n)), sep=' ')
except Exception as e:
	print(e)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	i = 1
	j = n
	res = []
	for k in range(n):
		if k % 2 == 0:
			print(i, end=' ')
			i += 1
		else:
			print(j, end=' ')
			j -= 1
	print()


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


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


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


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


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


def readInt():
	return int(input())

def readIntList():
	return list(map(int, input().split()))

def readStringList():
	return list(input())

def readStringListWithSpace():
	return list(input().split())

def readString():
	return input()
import math
TC = readInt()
for tc in range(TC):
	n = readInt()
	res = [1]
	for i in range(3, n + 1):
		res.append(i)
	res.append(2)
	print(*res)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	ans = [1]
	for i in range(n, 1, -1):
		ans.append(i)
	print(*ans)


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


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


for _ in range(int(input())):
	n = int(input())
	l = [1]
	a = list(range(2, n + 1))
	a = a[::-1]
	l = l + a
	print(*l)


def nc2(n):
	return n * (n - 1) // 2
t = int(input())
while t:
	t -= 1
	n = int(input())
	s = []
	e = []
	for i in range(n // 2):
		s.append(i + 1)
		s.append(n - i)
	if n % 2 != 0:
		s.append(n // 2 + 1)
	print(*s)


for _ in range(int(input())):
	a = int(input())
	print(1, end=' ')
	for i in range(3, a + 1):
		print(i, end=' ')
	print(2)


for _ in range(int(input())):
	n = int(input())
	L = [0] * n
	for j in range(n):
		if j % 2 == 0:
			L[j // 2] = j + 1
		else:
			L[n - 1 - j // 2] = j + 1
	print(' '.join(map(str, L)))


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(i + 1)
	(arr[1], arr[-1]) = (arr[-1], arr[1])
	print(*arr)


import math
t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = []
	for i in range(n):
		if i % 2 == 0:
			arr.append(i + 1)
	for i in range(n - 1, -1, -1):
		if i % 2 != 0:
			arr.append(i + 1)
	print(*arr)


for _ in range(int(input())):
	n = int(input())
	a = ''
	for i in range(1, n + 1):
		if i != 2:
			a += str(i) + ' '
	a += '2'
	print(a)


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


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


for t in range(int(input())):
	n = int(input())
	print(1, end=' ')
	for i in reversed(range(2, n + 1)):
		print(i, end=' ')
	print()