JJ gives you a number N and challenges you to construct a permutation P of length N such that:
|P_{i + 1} - P_{i}| ≥ 2 for all 1 ≤ i ≤ N - 1 (Here |x| denotes the absolute value of x)

Can you complete JJ's challenge?

As a reminder, a permutation of length N is an array where every integer from 1 to N occurs exactly once.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains one integer N — the length of the permutation P to be constructed.

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

For each test case, output N space-separated integers P_{1}, P_{2}, \ldots, P_{N} denoting the permutation P which satisfies the given conditions.

If no such permutation exists, output -1.

If there are multiple answers, print any.

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

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

----- Sample Input 1 ------ 
2
2
6

----- Sample Output 1 ------ 
-1
1 4 2 5 3 6

----- explanation 1 ------ 
Test Case 1: It can be proven that no permutation of length $2$ exists that satisfies the given conditions.

Test Case 2: $[1, 4, 2, 5, 3, 6]$ satisfies the given condition, since $|P_{i + 1} - P_{i}| ≥ 2$ for all $1 ≤ i ≤ N - 1$

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
t = int(input())
for ni in range(t):
	n = int(input())
	if n <= 3:
		print(-1)
	elif n == 4:
		print('3 1 4 2')
	elif n % 2 == 0:
		l1 = [int(i) for i in range(1, n, 2)]
		l2 = [int(i) for i in range(2, n + 1, 2)]
		print(*l1, end=' ')
		print(*l2)
	else:
		l1 = [int(i) for i in range(1, n + 1, 2)]
		l2 = [int(i) for i in range(2, n, 2)]
		print(*l1, end=' ')
		print(*l2)


for _ in range(int(input())):
	n = int(input())
	if n < 4:
		print(-1)
	elif n == 4:
		print('3 1 4 2')
	elif n == 5:
		print('3 1 4 2 5')
	else:
		(i, j) = (1, (n + 1) // 2 + 1)
		while n > 0:
			if n == 1:
				print(i, end='')
			else:
				print(i, j, end=' ')
			i += 1
			j += 1
			n -= 2
		print()


for _ in range(int(input())):
	N = int(input())
	if N <= 3:
		print(-1)
		continue
	A = list(range(2, N + 1, 2)) + list(range(1, N + 1, 2))
	print(*A)


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


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


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


for tc in range(int(input())):
	n = int(input())
	i = 1
	p = list(range(1, n + 1))
	a = []
	odd = 0
	if n % 2 == 0:
		mid = n // 2
	else:
		odd = 1
		mid = n // 2 + 1
	if n <= 3:
		print(-1)
	elif n == 4:
		print(2, 4, 1, 3)
	else:
		for i in range(n // 2):
			a.append(p[i])
			a.append(p[i + mid])
		if odd == 1:
			a.append(p[n // 2])
		print(*a)


t = int(input())
for t in range(t):
	n = int(input())
	if n <= 3:
		print(-1)
	elif n == 4:
		print('2 4 1 3')
	else:
		s = []
		a = 1
		b = n - n // 2 + 1
		for i in range(1, n + 1):
			if i % 2 == 1:
				s.append(str(a))
				a += 1
			else:
				s.append(str(b))
				b += 1
		print(' '.join(s))


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n < 4:
		print(-1)
	elif n == 4:
		print('2 4 1 3')
	else:
		d = math.ceil(n / 2)
		for i in range(1, d + 1):
			print(i, end=' ')
			if d + i <= n:
				print(d + i, end=' ')


for _ in range(int(input())):
	n = int(input())
	s = ''
	if n < 4:
		print(-1)
	elif n == 4:
		print('2 4 1 3')
	else:
		for i in range(1, n + 1, 2):
			s += str(i)
			s += ' '
		for i in range(2, n + 1, 2):
			s += str(i)
			s += ' '
		print(s)


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


testcase = int(input())
for _ in range(testcase):
	n = int(input())
	if n <= 3:
		print('-1')
	else:
		str1 = [x for x in range(2, n + 1, 2)]
		str2 = [x for x in range(1, n + 1, 2)]
		print(*str1 + str2)


T = int(input())
for i in range(T):
	N = int(input())
	if N <= 3:
		print(-1)
	elif N == 4:
		print('3 1 4 2')
	else:
		for j in range(1, N + 1, 2):
			print(j, end=' ')
		for k in range(2, N + 1, 2):
			print(k, end=' ')


for _ in range(int(input())):
	n = int(input())
	if n <= 3:
		print(-1)
		continue
	print(*range(2, n + 1, 2), *range(1, n + 1, 2))


for ii in range(int(input())):
	A = int(input())
	if A < 4:
		print(-1)
	elif A == 4:
		print(3, 1, 4, 2)
	elif A % 2 != 0:
		Rem = int(A / 2) + 1
		Rem1 = Rem - 1
		count = 0
		a = 1
		for j in range(A):
			print(a, end=' ')
			count += 1
			if count % 2 != 0:
				a += Rem
			else:
				a -= Rem1
	else:
		Rem = int(A // 2)
		Rem1 = Rem - 1
		count = 0
		a = 1
		for j in range(A):
			print(a, end=' ')
			count += 1
			if count % 2 != 0:
				a += Rem
			else:
				a -= Rem1
	print()


t = int(input())
for i in range(t):
	n = int(input())
	if n == 3 or n == 2:
		print(-1)
	else:
		s1 = [y for y in range(n - 1, 0, -2)]
		s2 = [x for x in range(n, 0, -2)]
		s1.extend(s2)
		print(*s1)


t = int(input(''))
if 1 <= t <= 10 ** 5:
	for _ in range(t):
		n = int(input(''))
		if 2 <= n <= 10 ** 5:
			if n < 4:
				print(-1)
			elif n == 4:
				print('3 1 4 2')
			else:
				z = 1
				a = []
				y = int(n / 2 + 0.5)
				x = 1
				for i in range(y):
					a.append(x)
					x += 1
				for i in range(1, n, 2):
					a.insert(i, x)
					x += 1
				for x in a:
					print(x, end=' ')


for _ in range(int(input())):
	n = int(input())
	l = []
	m = []
	if n <= 3:
		print('-1')
	elif n == 4:
		print('2 4 1 3')
	else:
		for i in range(1, n + 1):
			if i % 2 != 0:
				l.append(i)
			m.append(i)
		x = set(m).symmetric_difference(set(l))
		v = l + list(x)
		print(' '.join([str(e) for e in v]))


for z in range(int(input())):
	n = int(input())
	l = []
	l.append(1)
	if n % 2 == 0:
		a = n // 2
		b = a - 1
	else:
		b = n // 2
		a = b + 1
	if n < 4:
		print(-1)
	elif n == 4:
		print('2 4 1 3')
	elif n % 2 == 1:
		for i in range(1, n, 2):
			l.append(l[i - 1] + a)
			l.append(l[i] - b)
		for y in range(len(l)):
			print(l[y], end=' ')
	else:
		for i in range(1, n - 1, 2):
			l.append(l[i - 1] + a)
			l.append(l[i] - b)
		l.append(l[n - 2] + a)
		for y in range(len(l)):
			print(l[y], end=' ')


import math
for _ in range(int(input())):
	n = int(input())
	if n < 4:
		print(-1)
	else:
		l = []
		i = math.ceil(n / 2)
		j = n
		while i != 0:
			if i == 1:
				l.append(1)
				if n & 1 == 0:
					l.append(j)
			else:
				l.append(i)
				l.append(j)
			i = i - 1
			j = j - 1
		print(*l)


from itertools import permutations
casos = int(input())
for i in range(casos):
	numero = int(input())
	if numero <= 3:
		print('-1')
	elif numero == 4:
		print('2 4 1 3 ')
	else:
		lista = [0] * numero
		k = 1
		for i in range(0, numero, 2):
			lista[i] = k
			k += 1
		for i in range(1, numero, 2):
			lista[i] = k
			k += 1
		for i in lista:
			print(i, end=' ')


T = int(input())
for i in range(T):
	N = int(input())
	odd = []
	even = []
	for j in range(1, N + 1):
		if j % 2 != 0:
			odd.append(j)
		else:
			even.append(j)
	if N < 4:
		print(-1)
	else:
		print(*even, *odd)


for _ in range(int(input())):
	print('-1' if (s := int(input())) < 4 else ' '.join([str(x) for x in list(range(2, s + 1, 2)) + list(range(1, s + 1, 2))]))


for _ in range(int(input())):
	n = int(input())
	if n < 4:
		print(-1)
	else:
		odd = []
		even = []
		for i in range(1, n + 1):
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		for i in odd[::-1]:
			print(i, end=' ')
		for i in even[::-1]:
			print(i, end=' ')
		print()


def ans(n):
	if n <= 3:
		return [-1]
	elif n == 4:
		return [2, 4, 1, 3]
	elif n % 2 == 0:
		arr = [0 for i in range(n)]
		arr[0] = 1
		arr[-1] = n
		i = 0
		j = n - 1
		while i < j:
			if arr[i] < arr[j]:
				t1 = arr[i] + 1
				t2 = arr[j] - 1
				arr[i + 1] = t2
				arr[j - 1] = t1
			else:
				t1 = arr[i] - 1
				t2 = arr[j] + 1
				arr[i + 1] = t2
				arr[j - 1] = t1
			i += 1
			j -= 1
		temp = arr[i - 1]
		temp2 = arr[j + 1]
		arr.remove(temp)
		arr.remove(temp2)
		arr.insert(0, temp)
		arr.insert(n - 1, temp2)
		return arr
	else:
		arr2 = ans(n - 1)
		arr2.append(n)
		return arr2
test_cases = int(input())
while test_cases != 0:
	d = int(input())
	print(*ans(d))
	test_cases -= 1


t = int(input())
while t > 0:
	n = int(input())
	if n >= 4:
		res = ''
		sub_res = ''
		for i in range(n, 0, -1):
			if i & 1 == 1:
				res += str(i) + ' '
			else:
				sub_res += str(i) + ' '
		print(res + sub_res)
	else:
		print(-1)
	t -= 1


tc = int(input())
for _ in range(tc):
	n = int(input())
	if n <= 3:
		print('-1')
	elif n == 4:
		print('3 1 4 2')
	else:
		arr = [0] * n
		if n % 2 == 0:
			for i in range(1, n // 2 + 1):
				arr[2 * i - 2] += i
			for i in range(n // 2 + 1, n + 1):
				j = i - n // 2
				arr[2 * j - 1] += i
		else:
			for i in range(1, n // 2 + 2):
				arr[2 * i - 2] += i
			for i in range(n // 2 + 2, n + 1):
				j = i - n // 2 - 1
				arr[2 * j - 1] += i
		for ele in arr:
			print(ele, end=' ')
		print()


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


t = int(input())
for _ in range(t):
	n = int(input())
	if n <= 3:
		print(-1)
	elif n == 4:
		print('2 4 1 3')
	else:
		result = []
		n1 = n
		if n1 % 2 != 0:
			n1 += 1
		for i in range(1, n1 // 2 + 1):
			result.extend([i, n1 // 2 + i])
		if n1 != n:
			result = result[:-1]
		print(' '.join(map(str, result)))


a = int(input())
for i in range(a):
	b = int(input())
	if b < 4:
		print(-1)
	elif b == 4:
		print('2 4 1 3')
	else:
		c = 1
		d = (b + 1) // 2 + 1
		for j in range(b):
			if j % 2 == 0:
				print(c, end=' ')
				c += 1
			else:
				print(d, end=' ')
				d += 1


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


for t in range(int(input())):
	n = int(input())
	l = []
	if n <= 3:
		print(-1)
	else:
		for i in range(1, n + 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 _ in range(int(input())):
	n = int(input())
	print(*([-1] if n < 4 else [i for i in range(2, n + 1, 2)] + [i for i in range(1, n + 1, 2)]))


t = int(input())
for i in range(t):
	n = int(input())
	p = []
	q = []
	if n <= 3:
		print(-1)
	elif n == 4:
		print('2 4 1 3')
	elif n % 2 == 0 and n != 4:
		m = n // 2
		for i in range(1, m + 1):
			print(i, i + m, end=' ')
	else:
		m = n // 2 + 1
		for i in range(1, m + 1):
			if i != m:
				print(i, i + m, end=' ')
			else:
				print(i)


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


tst = int(input())
for i in range(tst):
	n = int(input())
	a = int((n + 1) / 2)
	diff = n - a
	i = 1
	k = 2
	if n <= 3:
		print('-1')
	elif n == 4:
		print('3', '1', '4', '2')
	else:
		for j in range(a):
			print(i, end=' ')
			i = i + 2
		for j in range(diff):
			print(k, end=' ')
			k = k + 2
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	if n <= 3:
		print(-1)
	elif n == 4:
		print(*[2, 4, 1, 3], sep=' ')
	else:
		print(*[i for i in range(1, n + 1, 2)] + [i for i in range(2, n + 1, 2)], sep=' ')


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


from itertools import permutations
i = int(input().strip())
for j in range(i):
	x = int(input().strip())
	if x >= 4:
		j = 0
		k = 1
		for i in range(1, x + 1):
			j += 2
			if j <= x:
				print(j, end=' ')
				continue
			if k <= x:
				print(k, end=' ')
			else:
				break
			k += 2
	else:
		print(-1)


T = int(input())
for _ in range(T):
	N = int(input())
	if N > 4:
		a = []
		b = []
		for i in range(1, N + 1):
			if i % 2 == 0:
				a.append(str(i))
			else:
				b.append(str(i))
		b.extend(a)
		print(' '.join(b))
	elif N == 4:
		print('3 1 4 2')
	else:
		print('-1')


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


T = int(input())
while T > 0:
	N = int(input())
	if N < 4:
		print(-1)
	elif N == 4:
		A = [3, 1, 4, 2]
		print(*A, sep=' ')
	else:
		A = list()
		for i in range(1, N + 1):
			if i % 2 != 0:
				A.append(i)
		for i in range(1, N + 1):
			if i % 2 == 0:
				A.append(i)
		print(*A, sep=' ')
	T -= 1


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n < 4:
		print(-1)
	else:
		if n % 2 == 0:
			odd = n - 1
			even = n
		else:
			odd = n
			even = n - 1
		while odd > 0:
			print(odd, end=' ')
			odd -= 2
		while even > 0:
			print(even, end=' ')
			even -= 2
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 4:
		print(3, 1, 4, 2)
	elif n >= 5:
		cnt = 1
		for i in range(1, n + 1):
			if i % 2 != 0:
				print(cnt, end=' ')
			elif i % 2 == 0 and n % 2 != 0:
				print(n // 2 + cnt + 1, end=' ')
				cnt += 1
			elif i % 2 == 0 and n % 2 == 0:
				print(n // 2 + cnt, end=' ')
				cnt += 1
		print()
	else:
		print(-1)


for i in range(int(input())):
	c = []
	f = []
	a = int(input())
	if a > 4:
		if a % 2 == 1:
			l = list(range(1, a + 1))
			v = l.pop(len(l) // 2)
			x = int((len(l) - 2) / 2)
			y = [0] + list(range(1, x + 1, 1)) + list(range(-x, 0, 1))
			y.append(0)
			k = list(range(0, a - 1))
			for i in range(a - 1):
				c.append(y[i] + k[i])
			s = l.copy()
			for i in range(a - 1):
				l[c[i]] = s[i]
			print(*[v] + l)
		else:
			l = list(range(1, a + 1))
			x = int((len(l) - 2) / 2)
			y = [0] + list(range(1, x + 1, 1)) + list(range(-x, 0, 1))
			y.append(0)
			k = list(range(0, a))
			for i in range(a):
				c.append(y[i] + k[i])
			s = l.copy()
			for i in range(a):
				l[c[i]] = s[i]
			print(*l)
	elif a == 4:
		print(*[3, 1, 4, 2])
	else:
		print(-1)


def makepermuation(num):
	if num < 4:
		result = [-1]
	elif num == 4:
		result = [3, 1, 4, 2]
	elif num % 2 == 0:
		result = []
		half_num = int(num / 2)
		for i in range(1, half_num + 1):
			result.append(i)
			result.append(i + half_num)
	else:
		result = []
		half_num = num // 2 + 1
		for i in range(1, half_num + 1):
			result.append(i)
			result.append(i + half_num)
		result.pop()
	return result
T = int(input())
for k in range(T):
	N = int(input())
	ans = makepermuation(N)
	res = ''
	for n in ans:
		res += str(n)
		res += ' '
	res = res[:-1]
	print(res)


t = int(input())
while t > 0:
	n = int(input())
	o = 0
	e = 0
	if n % 2 == 0:
		e = n
		o = n - 1
	else:
		e = n - 1
		o = n
	if n == 2 or n == 3:
		print(-1)
	else:
		a = [x for x in range(o, 0, -2)]
		while e > 0:
			a.append(e)
			e -= 2
		for i in range(len(a)):
			print(a[i], end=' ')
	t -= 1


from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input().strip())):
	n = inp_int()
	if n < 4:
		print('-1')
	elif n == 4:
		for i in range(2, n + 1, 2):
			print(i, end=' ')
		for i in range(1, n + 1, 2):
			print(i, end=' ')
		print()
	else:
		for i in range(1, n + 1, 2):
			print(i, end=' ')
		for i in range(2, n + 1, 2):
			print(i, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	if n < 4:
		print(-1)
	elif n == 4:
		print(3, 1, 4, 2, sep=' ')
	else:
		l = [int(x) for x in range(1, n + 1)]
		if n % 2 == 0:
			l1 = l[:n // 2]
			l2 = l[n // 2:]
		else:
			l1 = l[:n // 2 + 1]
			l2 = l[n // 2 + 1:]
		l3 = []
		for x in range(n):
			try:
				if l1[x]:
					l3.append(l1[x])
				if l2[x]:
					l3.append(l2[x])
			except:
				pass
		print(*l3)


t = int(input())
for i in range(t):
	n = int(input())
	if n < 4:
		print(-1)
	elif n == 4:
		print('3 1 4 2')
	else:
		m = 0
		if n % 2 == 0:
			m = n // 2
		else:
			m = n // 2 + 1
		l1 = [x for x in range(1, m + 1)]
		l2 = [x for x in range(m + 1, n + 1)]
		s = ' '.join((f'{x} {y}' for (x, y) in zip(l1, l2)))
		if n % 2 != 0:
			s += ' ' + str(l1[-1])
		print(s)


t = int(input())
for g in range(t):
	a = int(input())
	if a < 4:
		print(-1)
	elif a == 4:
		print(3, 1, 4, 2, end='')
	else:
		for i in range((a + 1) // 2):
			print((i + 1) * 2 - 1, end=' ')
		for i in range(a // 2):
			print((i + 1) * 2, end=' ')
	print()


t = int(input())
for h in range(t):
	n = int(input())
	output = []
	if n < 4:
		print(-1)
	else:
		if n % 2 == 1:
			output.append(n)
		n = n // 2
		for i in range(1, n + 1):
			output.append(n + i)
			output.append(i)
	for i in output:
		if i != output[-1]:
			print(i, end=' ')
		else:
			print(i)


for i in range(int(input())):
	n = int(input())
	if n < 4:
		print(-1)
		continue
	temp = n
	n = n // 2
	for i in range(1, n + 1):
		print(n + i, end=' ')
		print(i, end=' ')
	if temp & 1:
		print(temp)


for i in range(int(input())):
	n = int(input())
	if n <= 3:
		print(-1)
	else:
		e = [int(i) for i in range(2, n + 1, 2)]
		o = [int(i) for i in range(1, n + 1, 2)]
		e = e[::-1]
		o = o[::-1]
		o.extend(e)
		print(*o)


t = int(input())
for _ in range(t):
	n = int(input())
	if n < 4:
		print(-1)
	else:
		even = [int(i) for i in range(2, n + 1, 2)]
		odd = [int(i) for i in range(1, n + 1, 2)]
		even = even[::-1]
		odd = odd[::-1]
		odd.extend(even)
		print(*odd)