For a permutation P of length N, we define L(P) to be the length of the longest increasing subsequence in P. That is, L(P) is the largest integer K such that there exist indices i_{1} < i_{2} < \ldots < i_{K} such that P_{i_{1}} < P_{i_{2}} < \ldots < P_{i_{K}}. 

Define P^{R} to be the permutation (P_{N}, P_{N-1}, \ldots, P_{1}). 

You are given a positive integer N. You need to output a permutation P of length N such that L(P) = L(P^{R}), or say that none exist.

Note: P is said to be a permutation of length N if P is a sequence of length N consisting of N distinct integers between 1 and N. For example, (3, 1, 2) is a permutation of length 3, but (1, 4, 2), (2, 2, 3) and (2, 1) are not.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line containing one integer N — the length of the permutation to be constructed.

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

For each test case, output on a new line "YES" if there exists a valid permutation, and "NO" if there doesn't. If you outputted "YES", on the next line, output a valid permutation P as N space-separated integers, the i^{th} of which is P_{i}.

You can print each letter of the string in any case (upper or lower) (for instance, strings YES, yEs, and yes will be considered identical).

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 2 \cdot 10^{5}$
- The sum of $N$ across all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
2
2
3
----- Sample Output 1 ------ 
NO
YES
1 3 2
----- explanation 1 ------ 
Test Case $1$: There are two permutations of length $2$ — $(1, 2)$ and $(2, 1)$. The length of the LIS of $(1, 2)$ is $2$ and the length of the LIS of $(2, 1)$ is $1$. Since these permutations are reverses of each other and have unequal LIS lengths, there is no valid permutation of length $2$.

Test Case $2$: The length of the LIS of $(1, 3, 2)$ is $2$, and the length of the LIS of its reverse, $(2, 3, 1)$, is also $2$. Therefore, this is a valid permutation of length $3$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Greedy algorithms


Solutions:
for _ in range(int(input())):
	n = int(input())
	if n != 2:
		print('YES')
		if n == 1:
			print(1)
		else:
			a = [i for i in range(n, n // 2 + n % 2, -1)] + [i for i in range(1, (n + 1) // 2 + 1)]
			if n % 2 == 0:
				(a[0], a[1]) = (a[1], a[0])
			print(*a)
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	if n == 2:
		print('NO')
	else:
		print('YES')
		if n % 2 == 1:
			ans = [i for i in range(1, n // 2 + 1)]
			for i in range(n, n // 2, -1):
				ans.append(i)
		else:
			ans = [i for i in range(2, n // 2 + 1)]
			ans.append(1)
			for i in range(n, n // 2, -1):
				ans.append(i)
		for num in ans:
			print(num, end=' ')
		print('\n')
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print('NO')
	else:
		print('YES')
		if n % 2 == 1:
			L = [i for i in range(1, n // 2 + 1)]
			for i in range(n, n // 2, -1):
				L.append(i)
			print(*L)
		else:
			L = [i for i in range(2, n // 2 + 1)]
			L.append(1)
			for i in range(n, n // 2, -1):
				L.append(i)
			print(*L)


def solve(n):
	if n == 2:
		return 'NO'
	if n == 3:
		return 'YES\n1 3 2'
	left = [2, 4]
	if n % 2 == 0:
		right = [3, 1]
		for _ in range(2, n // 2):
			left.append(left[-1] + 2)
			right.append(5 if right[-1] == 1 else right[-1] + 2)
	else:
		right = [1, 3]
		for _ in range(2, n // 2):
			left.append(left[-1] + 2)
			right.append(right[-1] + 2)
	right.reverse()
	middle = []
	if n % 2 == 1:
		middle = [n]
	return 'YES\n' + ' '.join(map(str, left + middle + right))
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('NO')
	elif n == 4:
		print('YES')
		ans = [3, 4, 1, 2]
		print(*ans)
	elif n % 2:
		ans = []
		for i in range(n // 2 + 1, n + 1):
			ans.append(i)
		for i in range(n // 2, 0, -1):
			ans.append(i)
		print('YES')
		print(*ans)
	else:
		ans = [3]
		for i in range(n - 1, 4, -2):
			ans.append(i)
		ans.append(2)
		ans.append(1)
		for j in range(6, n + 1, 2):
			ans.append(j)
		ans.append(4)
		print('YES')
		print(*ans)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		if n == 2:
			print('NO')
		elif n == 4:
			print('YES')
			print(' '.join(['3', '4', '1', '2']))
		else:
			print('YES')
			print(' '.join(['1'] + [str(i) for i in range(n // 2 + 2, n + 1)] + [str(i) for i in range(n // 2 + 1, 3, -1)] + ['2', '3']))
	else:
		print('YES')
		print(' '.join([str(i) for i in range(1, n + 1, 2)]) + ' ' + ' '.join([str(i) for i in range(n - 1, 1, -2)]))


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	n = nmbr()
	if n == 2:
		print('NO')
	else:
		a = [i for i in range(1, n + 1)]
		pos = n // 2
		a = a[:pos] + a[pos:][::-1]
		if n & 1 == 0:
			(a[pos - 1], a[pos - 2]) = (a[pos - 2], a[pos - 1])
		print('YES')
		print(*a)


t = int(input())
for i in range(t):
	t1 = t2 = 0
	l3 = [1, 3, 2]
	l4 = [2, 1, 4, 3]
	n = int(input())
	if n == 2:
		print('NO')
	elif n % 2 == 0:
		t1 = n - 4
		k1 = 4
		l = l4
		while t1 > 0:
			l.append(k1 + 1)
			l.insert(0, k1 + 2)
			k1 = k1 + 2
			t1 = t1 - 2
		print('YES')
		for j in l:
			print(j, sep=' ', end=' ')
		print()
	else:
		t2 = n - 3
		k = 3
		l = l3
		while t2 > 0:
			l.append(k + 1)
			l.insert(0, k + 2)
			k = k + 2
			t2 = t2 - 2
		print('YES')
		for j in l:
			print(j, sep=' ', end=' ')
		print()


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


for _ in range(int(input())):
	n = int(input())
	if n > 2:
		print('YES')
		ans3 = [1, 3, 2]
		ans4 = [2, 1, 4, 3]
		odd = []
		even = []
		if n & 1:
			for i in range(4, n + 1):
				if i & 1:
					odd.append(i)
				else:
					even.append(i)
			even = even[::-1]
			print(*even + ans3 + odd)
		else:
			for i in range(5, n + 1):
				if i & 1:
					odd.append(i)
				else:
					even.append(i)
			odd = odd[::-1]
			print(*odd + ans4 + even)
	else:
		print('NO')


import itertools
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('NO')
	else:
		print('YES')
		if n % 2 == 1:
			ans = [i + 1 for i in range(n // 2)]
			ans += [i for i in range(n, n // 2, -1)]
			print(*ans)
		elif n == 4:
			print('2 1 4 3')
		else:
			ans = [n // 2] + [i for i in range(1, n // 2)] + [i for i in range(n, n // 2, -1)]
			print(*ans)


from sys import stdin, stdout
t = int(stdin.readline().rstrip())
while t > 0:
	n = int(stdin.readline().rstrip())
	if n == 2:
		print('NO')
	elif n % 2 == 0:
		print('YES')
		array_odd = []
		for i in range(1, n):
			if i % 2 == 0:
				array_odd.append(i)
			else:
				array_odd.insert(0, i)
		array_odd.insert(n // 2, n)
		print(*array_odd)
	else:
		array = list(range(1, n + 1))
		array1 = array[:n // 2]
		array2 = array[n // 2:][::-1]
		print('YES')
		array = array1 + array2
		print(*array)
	t -= 1


for t in range(int(input())):
	n = int(input())
	flag = 0
	if n == 2:
		print('NO')
		continue
	if n & 1:
		a = [1, 3, 2]
		flag = 1
	else:
		a = [2, 1, 4, 3]
		flag = 0
	if flag == 1:
		for i in range(4, n + 1, 2):
			a.insert(0, i)
			a.append(i + 1)
	else:
		for i in range(5, n + 1, 2):
			a.insert(0, i)
			a.append(i + 1)
	print('YES')
	print(*a)


import sys
import bisect
inp = sys.stdin.readline

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	n = int(input())
	if n == 2:
		print('NO', end=' ')
	elif n % 2:
		print('YES')
		for i in range(1, n // 2 + 1):
			print(i, end=' ')
		for i in range(n, n // 2, -1):
			print(i, end=' ')
	else:
		print('YES')
		print(2, 1, end=' ')
		for i in range(3, n // 2 + 1):
			print(i, end=' ')
		for i in range(n, n // 2, -1):
			print(i, end=' ')
	print()


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


try:
	t = int(input())
	foundation = []
	while t:
		n = int(input())
		if n > 2:
			print('YES')
			g = n
			g = g - 1
			if n % 2 == 0:
				while g != 3:
					print(g, end=' ')
					g = g - 2
				print('2 1 4 3', end=' ')
				g = 6
				while g != n + 2:
					print(g, end=' ')
					g = g + 2
				print()
			else:
				while g != 2:
					print(g, end=' ')
					g = g - 2
				print('1 3 2', end=' ')
				g = 5
				while g != n + 2:
					print(g, end=' ')
					g = g + 2
				print()
		else:
			print('NO')
		t = t - 1
except:
	pass


def solve():
	n = int(input())
	l = []
	if n <= 2:
		print('NO')
		return
	print('YES')
	if n & 1:
		for i in range(1, n // 2 + 1):
			l.append(i)
		for i in range(n, n // 2, -1):
			l.append(i)
		print(*l)
		return
	for i in range(2, n // 2 + 1):
		l.append(i)
	l.append(1)
	for i in range(n, n // 2, -1):
		l.append(i)
	print(*l)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print('NO')
	else:
		print('YES')
		even_series = [2, 1, 4, 3]
		odd_series = [1, 3, 2]
		if n % 2 == 0:
			for i in range(5, n + 1, 2):
				even_series.append(i + 1)
				even_series.insert(0, i)
			print(*even_series)
		else:
			for i in range(4, n + 1, 2):
				odd_series.append(i + 1)
				odd_series.insert(0, i)
			print(*odd_series)


def func():
	n = int(input())
	if n == 2:
		print('NO')
	elif n % 2:
		print('YES')
		for i in range(1, n // 2 + 1):
			print(i, end=' ')
		for i in range(n, n // 2, -1):
			print(i, end=' ')
		print()
	else:
		print('YES')
		print(n // 2, end=' ')
		for i in range(1, n // 2):
			print(i, end=' ')
		for i in range(n, n // 2, -1):
			print(i, end=' ')
		print()
t = int(input())
for i in range(t):
	func()


t = int(input())
for test in range(t):
	n = int(input())
	if n == 2:
		print('NO')
		continue
	elif n % 2 == 1:
		ans = [0] * n
		i = 1
		j = 0
		k = n - 1
		while j <= k:
			if j == k:
				ans[j] = i
				i += 1
				break
			ans[j] = i
			i += 1
			ans[k] = i
			i += 1
			j += 1
			k -= 1
		print('YES')
		print(*ans)
	else:
		ans = [0] * n
		val = n // 2
		i = 2
		j = 0
		while i != val + 1:
			ans[j] = i
			i += 1
			j += 1
		ans[val - 1] = 1
		j += 1
		i = n
		while j < n:
			ans[j] = i
			i -= 1
			j += 1
		print('YES')
		print(*ans)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 2:
		print('NO')
	else:
		print('YES')
		if n % 2 == 1:
			for i in range(n // 2):
				print(i + 1, end=' ')
			for i in range(n // 2 + 1):
				print(n - i, end=' ')
		else:
			for i in range(n // 2 - 2):
				print(i + 1, end=' ')
			print(str(n // 2) + ' ' + str(n // 2 - 1), end=' ')
			for i in range(n // 2):
				print(n - i, end=' ')


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def hnbhai(tc):
	n = sb()
	if n == 2:
		print('NO')
		return
	print('YES')
	if n % 2:
		ans = [i for i in range(1, n // 2 + 1)] + [i for i in range(n, n // 2, -1)]
	else:
		ans = [i for i in range(2, n // 2 + 1)] + [1] + [i for i in range(n, n // 2, -1)]
	print(*ans)
	return
for _ in range(sb()):
	hnbhai(_ + 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(1, n + 1):
		l.append(i)
	if n == 2:
		print('NO')
	else:
		if n % 2 != 0:
			mid = n // 2 + 1
			x = l[:mid - 1] + l[mid - 1:][::-1]
		elif n % 2 == 0:
			mid = n // 2
			x = l[1:mid] + [1, n] + l[mid:n - 1][::-1]
		print('YES')
		for i in range(n):
			print(x[i], end=' ')
		print()


T = int(input())
for i in range(T):
	n = int(input())
	if n <= 2:
		print('NO', end='')
	else:
		print('YES')
		if n % 2 != 0:
			for x in range(1, n // 2 + 1):
				print(x, end=' ')
			for t in range(n, n // 2, -1):
				print(t, end=' ')
		else:
			print(n - 1, end=' ')
			for x in range(1, n - 2, 2):
				print(x, end=' ')
			for t in range(n, 1, -2):
				print(t, end=' ')
	print()


for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print('YES')
		print(1)
	elif N == 2:
		print('NO')
	elif N % 2 != 0:
		print('YES')
		print(*list(range(N, (N + 1) // 2, -1)) + list(range(1, (N + 3) // 2)))
	else:
		print('YES')
		l = [1]
		l.append(N)
		print(*list(range(N - 1, N // 2, -1)) + l + list(range(2, N // 2 + 1)))


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


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('NO')
	elif n % 2 == 0:
		o = []
		e = []
		print('YES')
		for i in range(1, n + 1):
			if i % 2 != 0:
				o.append(i)
			else:
				e.append(i)
		x = o.pop()
		print(x, end=' ')
		for i in o:
			print(i, end=' ')
		for i in e[::-1]:
			print(i, end=' ')
		print()
	else:
		o = []
		e = []
		print('YES')
		for i in range(1, n + 1):
			if i % 2 != 0:
				o.append(i)
			else:
				e.append(i)
		for i in o:
			print(i, end=' ')
		for i in e[::-1]:
			print(i, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	if n & 1:
		print('YES')
		for i in range(1, n // 2 + 1):
			print(i, end=' ')
		for j in range(n, n // 2, -1):
			print(j, end=' ')
		print()
	elif n != 2:
		print('Yes')
		print(n // 2, end=' ')
		for i in range(1, n // 2):
			print(i, end=' ')
		for j in range(n, n // 2, -1):
			print(j, end=' ')
		print()
	else:
		print('NO')


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


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


for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print('NO')
	elif n % 2 != 0:
		even = []
		odd = []
		for i in range(1, n + 1):
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		print('YES')
		print(*odd, *even[::-1])
	else:
		l1 = list(range(1, n // 2 + 1))
		l3 = list(range(n // 2 + 1, n + 1))
		l2 = l3[::-1]
		temp = l2[0] + l2[1]
		l2[0] = temp - l2[0]
		l2[1] = temp - l2[1]
		print('YES')
		print(*l2, *l1)


T = int(input())
for i in range(T):
	N = int(input())
	if N == 2:
		print('NO')
	else:
		if N % 2 == 0:
			K = N - 1
		else:
			K = N
		l = list(range(1, K + 1))
		a = l[0:int(K / 2)]
		b = l[int(K / 2):]
		b = b[::-1]
		c = a + b
		print('YES')
		if N % 2 == 0:
			d = [c[-1]] + [N] + c[0:-1]
			c = d
		print(*c)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	if n == 2:
		print('NO')
		continue
	if n % 2 == 0:
		print('YES')
		arr = [n // 2]
		for i in range(1, n // 2):
			arr.append(i)
		for i in range(n, n // 2, -1):
			arr.append(i)
		print(*arr)
		continue
	l = math.ceil(n / 2)
	arr = []
	for i in range(n, l, -1):
		arr.append(i)
	for i in range(1, l + 1):
		arr.append(i)
	print('YES')
	print(*arr)


t = int(input())

def solve(n):
	ans = []
	if n & 1 == 1:
		i = 1
		while i < n // 2 + 1:
			ans.append(i)
			i += 1
		i = n
		while i > n // 2:
			ans.append(i)
			i -= 1
	else:
		i = 1
		ans.append(n // 2)
		while i < n // 2:
			ans.append(i)
			i += 1
		i = n
		while i > n // 2:
			ans.append(i)
			i -= 1
	return ans
for _ in range(t):
	x = int(input())
	if x == 2:
		print('NO')
		continue
	ans = solve(x)
	print('YES')
	for i in ans:
		print(i, end=' ')
	print('\n')


def xxx(N):
	if N % 2 == 0:
		k = N // 2
		for i in range(1, k):
			print(2 * i + 1, end=' ')
		print(1, end=' ')
		for i in range(k, 0, -1):
			print(2 * i, end=' ')
		print('')
	else:
		k = (N - 1) // 2
		print(1, end=' ')
		for i in range(1, k + 1):
			print(2 * i + 1, end=' ')
		for i in range(k, 0, -1):
			print(2 * i, end=' ')
		print('')
for _ in range(int(input())):
	N = int(input())
	if N == 2:
		print('NO')
	else:
		print('YES')
		xxx(N)


n = int(input())
for i in range(n):
	n1 = int(input())
	list1 = []
	count = 1
	if n1 == 2:
		print('NO')
	else:
		print('YES')
		i = 0
		j = n1 - 1
		san = True
		for k in range(n1):
			list1.insert(k, 0)
		while i <= j:
			if san:
				list1[i] = count
				i = i + 1
				san = False
			else:
				list1[j] = count
				j = j - 1
				san = True
			count = count + 1
		if n1 % 2 == 0:
			print(list1[n1 // 2 - 1], end=' ')
			for i in list1:
				if i == list1[n1 // 2 - 1]:
					continue
				print(i, end=' ')
		else:
			for i in list1:
				print(i, end=' ')


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


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('NO')
	elif n == 4:
		print('YES')
		print(3, 1, 4, 2, sep=' ')
	elif n % 2 == 0:
		print('YES')
		print(1, end=' ')
		print(n - 1, n, sep=' ', end=' ')
		(s1, s2) = (2, n - 2)
		while s1 <= n // 2:
			print(s1, end=' ')
			if s2 > n // 2:
				print(s2, end=' ')
			s1 += 1
			s2 -= 1
		print()
	else:
		print('YES')
		(s1, s2) = (n, 1)
		while s2 < s1:
			print(s1, s2, sep=' ', end=' ')
			s1 -= 1
			s2 += 1
		print(s1)


for i in range(int(input())):
	n = int(input())
	half = n // 2
	if n == 2:
		print('NO')
	else:
		print('YES')
		if n % 2 == 0:
			ans = []
			for i in range(2, half + 1):
				ans.append(i)
			ans.append(1)
			for i in range(n, half, -1):
				ans.append(i)
		else:
			ans = [None for i in range(n)]
			ans[half] = n
			inc_dec = 1
			counter = 1
			while inc_dec <= half:
				if counter % 2 == 0:
					ans[half - inc_dec] = n - counter
					inc_dec += 1
				else:
					ans[half + inc_dec] = n - counter
				counter += 1
		print(' '.join((str(x) for x in ans)))


from math import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def rSort(arr1, arr2):
	(arr1, arr2) = [list(tuple) for tuple in zip(*sorted(arr1, arr2))]

class Pair:

	def __init__(self, a, b):
		self.a = a
		self.b = b

class Solution:

	def __init__(self):
		self.ans = 0

	def solve(self) -> None:
		n = inp()
		if n == 2:
			print('NO')
			return
		print('YES')
		if n & 1:
			for i in range(1, n // 2 + 1):
				print(i, end=' ')
			for i in range(n, n // 2, -1):
				print(i, end=' ')
		else:
			for i in range(2, n // 2 + 1):
				print(i, end=' ')
			print(1, end=' ')
			for i in range(n, n // 2, -1):
				print(i, end=' ')
		print()
t = 1
t = inp()
while t:
	t -= 1
	sol = Solution()
	sol.solve()


import math
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print('YES')
		print(1)
	elif n == 2:
		print('NO')
	elif n == 3:
		l = []
		l.append(1)
		l.append(3)
		l.append(2)
		print('YES')
		print(*l)
	else:
		l = []
		if n % 2 != 0:
			for i in range(1, int(n / 2) + 1):
				l.append(i)
			for i in range(n, int(n / 2), -1):
				l.append(i)
		else:
			l.append(2)
			for i in range(1, int(n / 2) + 1):
				if i == 2:
					continue
				else:
					l.append(i)
			for i in range(n, int(n / 2), -1):
				l.append(i)
		print('YES')
		print(*l)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2:
		print('YES')
		l = list(map(str, list(range(1, int(n / 2) + 1)) + list(range(n, int(n / 2), -1))))
		print(' '.join(l))
	elif n != 2:
		print('YES')
		l = [int(n / 2)] + [i for i in range(1, int(n / 2))] + [i for i in range(n, int(n / 2), -1)]
		l = list(map(str, l))
		print(' '.join(l))
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('YES')
		print(1)
	elif n % 2 != 0:
		print('YES')
		l = list(range(1, n + 1))
		l = l[:n // 2] + l[-1:n // 2 - 1:-1]
		print(*l)
	elif n != 2:
		print('YES')
		l = list(range(1, n + 1))
		ans = [l[n // 2 - 1]]
		ans += l[:n // 2 - 1] + l[-1:n // 2 - 1:-1]
		print(*ans)
	else:
		print('NO')


t = int(input())
test = []
for i in range(t):
	v = int(input())
	test.append(v)
for i in test:
	if i == 2:
		print('NO')
		continue
	print('YES')
	v = i // 2
	ls = []
	if i % 2 == 1:
		v += 1
	for j in range(v, 0, -1):
		ls.append(str(j))
	for j in range(v + 1, i + 1):
		ls.append(str(j))
	if i % 2 == 0:
		temp = ls[len(ls) - 1]
		ls[len(ls) - 1] = ls[len(ls) - 2]
		ls[len(ls) - 2] = temp
	print(' '.join(ls))


def front(j, strng):
	for i in range(1, j):
		strng += str(i) + ' '
	return strng

def back(n, j, strng):
	for i in range(n, j - 1, -1):
		strng += str(i) + ' '
	return strng
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('NO')
		continue
	print('YES')
	if n % 2 != 0:
		j = n // 2 + 1
		strng = ''
		temp = front(j, strng)
		temp = back(n, j, temp)
		print(temp)
	else:
		strng = ''
		strng += str(n // 2) + ' '
		j = n // 2
		temp = front(j, strng)
		temp = back(n, j + 1, temp)
		print(temp)


for _ in range(int(input())):
	num = int(input())
	if num == 2:
		print('NO')
		continue
	if num == 4:
		print('YES')
		print(2, 4, 1, 3)
		continue
	print('YES')
	if num % 2 == 0:
		for i in range(1, num - 1, 2):
			print(i, end=' ')
		print(num, num - 1, end=' ')
		for i in range(num - 2, 4, -2):
			print(i, end=' ')
		print(2, 4)
	else:
		for i in range(1, num // 2 + 1):
			print(i, end=' ')
		for i in range(num, num // 2, -1):
			print(i, end=' ')
		print('')


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


import sys
RW = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
from collections import defaultdict as df
import heapq
import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print('YES')
		print(*[1])
	elif n == 2:
		print('NO')
	elif n == 3:
		print('YES')
		print(*[1, 3, 2])
	elif n == 4:
		print('YES')
		print(*[2, 4, 1, 3])
	else:
		ans = [0] * n
		index = 0
		for i in range(1, 1 + (n + 1) // 2):
			ans[index] = i
			index += 2
		if n % 2 == 0:
			index = n - 1
		else:
			index = n - 2
		for i in range(1 + (n + 1) // 2, n + 1):
			ans[index] = i
			index -= 2
		print('YES')
		if n % 2 == 0:
			(ans[0], ans[2]) = (ans[2], ans[0])
		print(*ans)


for _ in range(int(input())):
	k = int(input())
	if k == 1:
		print('YES')
		print(1)
		continue
	if k == 2:
		print('NO')
		continue
	print('YES')
	if k % 2 == 1:
		a = [i for i in range(1, k + 1, 2)]
		b = [i for i in range(2, k, 2)]
		print(*a + b[::-1])
	else:
		a = [i for i in range(k // 2 + 1, k + 1)]
		a = a + [1]
		b = [i for i in range(2, k // 2 + 1)]
		print(*a + b[::-1])


t = int(input())
for zz in range(t):
	n = int(input())
	p = n // 2
	l = []
	l1 = []
	if n == 2:
		print('NO')
		continue
	if n % 2 == 0:
		x = n // 2
		print('YES')
		print(x, end=' ')
		for j in range(1, x):
			print(j, end=' ')
		for j in range(n, x, -1):
			print(j, end=' ')
		print()
	else:
		print('YES')
		for i in range(1, n + 1):
			if i <= p:
				l.append(i)
			else:
				l1.append(i)
		print(*l + l1[::-1])


from math import ceil
for i in range(int(input())):
	n = int(input())
	if n % 2:
		print('YES')
		for i in range(1, int(n / 2) + 1):
			print(i, end=' ')
		print(n, end=' ')
		for i in range(n - 1, int(n / 2), -1):
			print(i, end=' ')
		print()
	elif n != 2:
		print('YES')
		print(n // 2, end=' ')
		for i in range(1, n // 2):
			print(i, end=' ')
		for i in range(n, n // 2, -1):
			print(i, end=' ')
		print('')
	else:
		print('NO')


import sys
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('NO')
		continue
	print('YES')
	a = [0] * n
	if n & 1:
		(i, v) = (0, 1)
		while i < n:
			a[i] = v
			v += 1
			i += 2
		(i, v) = (1, n)
		while i < n:
			a[i] = v
			v -= 1
			i += 2
	else:
		(i, v) = (0, 1)
		while i < n:
			a[i] = v
			i += 2
			v += 1
		(i, v) = (1, n)
		while i < n:
			a[i] = v
			v -= 1
			i += 2
		(a[0], a[2]) = (a[2], a[0])
	print(*a)


for i in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print('YES')
		l = [i for i in range(1, n + 1)]
		x = [0] * n
		a = 0
		b = n - 1
		f = 0
		while f < n:
			x[a] = l[f]
			f += 1
			if f < n:
				x[b] = l[f]
			f += 1
			a += 1
			b -= 1
		for i in x:
			print(i, end=' ')
		print()
	elif n != 2:
		print('YES')
		print(n // 2, end=' ')
		for i in range(1, n // 2):
			print(i, end=' ')
		for i in range(n, n // 2, -1):
			print(i, end=' ')
		print()
	else:
		print('NO')


t = int(input())

def fun(lt, n):
	temp = []
	if n % 2 != 0:
		for i in range(0, n // 2):
			temp.append(lt[i])
		temp.append(lt.pop())
		for i in range(n - 2, n // 2 - 1, -1):
			temp.append(lt[i])
		for j in temp:
			print(j, end=' ')
		print(end='\n')
	elif n % 2 == 0:
		print(n // 2, end=' ')
		for i in range(1, n // 2):
			print(i, end=' ')
		for i in range(n, n // 2, -1):
			print(i, end=' ')
		print(end='\n')
for i in range(t):
	n = int(input())
	if n == 2:
		print('NO')
	else:
		lt = [j for j in range(1, 1 + n)]
		print('YES')
		fun(lt, n)


for _ in range(int(input())):
	z = int(input())
	if z > 2:
		if z % 2 == 0:
			m = []
			o = []
			h = [1]
			for i in range(2, z + 1):
				if i % 2 == 0:
					m.append(i)
				else:
					o.append(i)
			l = m + h + o[::-1]
		else:
			m = []
			o = []
			h = [z]
			for i in range(1, z):
				if i % 2 == 0:
					m.append(i)
				else:
					o.append(i)
			l = o + h + m[::-1]
		print('YES\n' + ' '.join([str(o) for o in l]))
	elif z == 2:
		print('NO')
	elif z == 1:
		print('YES')
		print('5')


for t in range(int(input())):
	N = int(input())
	if N == 2:
		print('NO')
		continue
	print('YES')
	ArraySoham = []
	for i in range(1, N // 2 + 1):
		ArraySoham.append(i)
	for i in range(N, N // 2, -1):
		ArraySoham.append(i)
	if N % 2 == 0:
		(ArraySoham[(N - 1) // 2], ArraySoham[(N - 1) // 2 - 1]) = (ArraySoham[(N - 1) // 2 - 1], ArraySoham[(N - 1) // 2])
	print(*ArraySoham)


try:
	for _ in range(int(input())):
		n = int(input())
		if n % 2 == 0:
			array = [k for k in range(n // 2 + 1, n + 1)]
			for ll in range(n // 2 - 1, 0, -1):
				array.append(ll)
			array.append(n // 2)
			ans = 'YES' if n != 2 else 'NO'
			print(ans)
			if ans == 'YES':
				print(*array)
		else:
			if n == 1:
				print('YES')
				print(1)
				continue
			elif n == 3:
				print('YES')
				print('1 3 2')
				continue
			cc = n // 2
			array = [1]
			b = [i for i in range(2, n // 2 + 1)]
			b = b[::-1]
			c = [j for j in range(n // 2 + 2, n)]
			array += c
			array.append(n)
			array += b
			array.append(n // 2 + 1)
			array[0] = array[-1]
			array[-1] = 1
			print('YES')
			print(*array)
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		if n < 3:
			print('NO')
		elif n == 4:
			print('YES')
			ar = []
			ar = [2, 1, 4, 3]
			print(*ar)
		else:
			print('YES')
			ar = []
			a = n // 2 - 2
			j = 1
			while j < a + 1:
				ar.append(j)
				j += 1
			ar.append(n)
			ar.append(j + 1)
			j = j + 1
			ar.append(j - 1)
			ar.append(n - 1)
			a = j
			j = n - 2
			while j > a:
				ar.append(j)
				j -= 1
			print(*ar)
	else:
		print('YES')
		ar = []
		j = 1
		while j < n + 1:
			ar.append(j)
			j += 1
			j += 1
		j = n - 1
		while j > 1:
			ar.append(j)
			j -= 1
			j -= 1
		print(*ar)