Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

For a positive, \textbf{even} integer N, we call a pair of arrays A and B to be interesting if they satisfy the following conditions :

|A| = |B| = N/2 i.e. the length of array A is equal to the length of array B.

Each integer from 1 to N occurs exactly once in exactly one of the arrays.

The i^{th} prefix sum of A is not equal to i^{th} prefix sum of B for all 1 ≤ i ≤ N/2-1. Formally, \displaystyle \sum_{j = 1}^{i} A_{j} \neq \sum_{j = 1}^{i} B_{j} for all 1 ≤ i ≤ N/2 - 1

Sum of all elements in A is equal to sum of all elements in B i.e. \displaystyle \sum_{j = 1}^{N/2} A_{j} = \sum_{j = 1}^{N/2} B_{j}

You are given a positive, even integer N. If there exists an interesting pair of arrays, then print "YES" followed by an interesting pair for this given N. If there exists multiple interesting pairs of arrays for given N, you can print any. Print "NO" in a single line if no such pair exists.

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

- First line of input will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single line of input, the integer N.

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

For each test case, if there exists an interesting pair of arrays, say (A, B), then in the first line print "YES", in the second line print array A separated by spaces, and in third line print array B separated by spaces. Print "NO" in a single line if no such pair exists. If there are multiple answers, print any of them.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$N$ is guaranteed to be even.
- Sum of $N$ over all test cases doesn't exceed $10^{6}$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
2
2
4
----- Sample Output 1 ------ 
NO
YES
1 4
2 3
----- explanation 1 ------ 
Test case 2: Consider $A = [1, 4]$ and $B = [2, 3]$. Every integer from $1$ to $4$ occurs exactly once in exactly one of the arrays. Also, $1$st prefix sum of $A$ is not equal to $1$st prefix sum of $B$ ($1 \neq 2$). And sum of the elements is equal to $5$ for both arrays. So, $(A, B)$ is an interesting pair.

Difficulty: MEDIUM
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	if n % 4 != 0:
		print('NO')
	else:
		print('YES')
		(l1, l2) = ([], [])
		for j in range(1, n + 1, 2):
			if j <= n // 2:
				l1.append(j)
				l2.append(j + 1)
			else:
				l2.append(j)
				l1.append(j + 1)
		for x in range(len(l1)):
			print(l1[x], end=' ')
		print()
		for y in range(len(l2)):
			print(l2[y], end=' ')
		print()


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


for tc in range(int(input())):
	n = int(input())
	poss = True
	if n % 4 != 0:
		poss = False
	if poss:
		mid = n // 2
		ans = []
		b = []
		for i in range(1, mid + 1):
			if i % 2 == 1:
				ans.append(i * 2 - 1)
				b.append(i * 2)
			else:
				ans.append(i * 2)
				b.append(i * 2 - 1)
	if poss:
		print('YES')
		print(*ans[1:] + [ans[0]])
		print(*b)
	else:
		print('NO')


t = int(input())
for t in range(t):
	n = int(input())
	if n % 4 != 0:
		print('NO')
	else:
		print('YES')
		(a, b) = ([], [])
		a.append(1)
		for i in range(2, n, 2):
			if i % 4 == 2:
				b.append(i)
				b.append(i + 1)
			else:
				a.append(i)
				a.append(i + 1)
		a.append(n)
		b.reverse()
		for j in a:
			print(j, end=' ')
		print()
		for k in b:
			print(k, end=' ')
		print()


for i in range(int(input())):
	n = int(input())
	if not n % 4 == 0:
		print('NO')
	else:
		print('YES')
		a = []
		b = []
		for i in range(1, n // 2 + 1):
			if i % 2 == 1:
				a.append(2 * i)
				b.append(2 * i - 1)
			else:
				a.append(2 * i - 1)
				b.append(2 * i)
		print(*a[1:] + [a[0]])
		print(*b)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 4 == 0:
		print('YES')
		r1 = [*range(1, n // 2 + 1)]
		r2 = [*range(n // 2 + 1, n + 1)][::-1]
		x1 = []
		x2 = []
		for i in range(n // 2):
			if i % 2 == 0:
				x2.append(r1[i])
				x2.append(r2[i])
			else:
				x1.append(r1[i])
				x1.append(r2[i])
		x1.sort()
		x2.sort()
		print(*x2)
		print(*x1)
	else:
		print('NO')


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


t = int(input(''))
for _ in range(t):
	n = int(input(''))
	if n % 4 != 0:
		print('NO')
		continue
	else:
		print('YES')
		a1 = []
		a2 = []
		a1.append(1)
		for i in range(2, n, 2):
			if i % 4 == 2:
				a2.append(i)
				a2.append(i + 1)
			else:
				a1.append(i)
				a1.append(i + 1)
		a1.append(n)
		a2.reverse()
		for i in range(n // 2):
			print(a1[i], end=' ')
		print()
		for i in range(n // 2):
			print(a2[i], end=' ')


for _ in range(int(input())):
	n = int(input())
	l1 = []
	l2 = []
	if n == 2:
		print('NO')
		continue
	if n * (n + 1) // 2 % 2 != 0:
		print('NO')
		continue
	else:
		k = n // 2 + 1
		for i in range(k - 1):
			if i + 1 == n // 2:
				l2.append(i + 1)
				l2.append(n - i)
				continue
			elif (i + 1) % 2 != 0:
				l1.append(i + 1)
				l1.append(n + 1 - (i + 1))
			else:
				l2.append(i + 1)
				l2.append(n + 1 - (i + 1))
		print('YES')
		l1 = sorted(l1)
		l2 = sorted(l2)
		for i in l1:
			print(i, end=' ')
		print()
		for j in l2:
			print(j, end=' ')
		print()


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


for _ in range(int(input())):
	n = int(input())
	if n % 4 == 0:
		print('YES')
		(l1, l2) = ([], [])
		f = n // 2
		for i in range(1, n + 1):
			if i > f:
				if i % 2 == 0:
					l1.append(i)
				else:
					l2.append(i)
			elif i % 2 == 1:
				l1.append(i)
			else:
				l2.append(i)
		print(*l1)
		print(*l2)
	else:
		print('NO')


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
for _ in range(int(input())):
	N = int(input())
	a = []
	b = []
	o = True
	if N % 4 != 0:
		print('NO')
		continue
	for i in range(N // 2):
		if o:
			a += [N - i, i + 1]
			o = not o
		else:
			b += [N - i, i + 1]
			o = not o
	print('YES')
	print(*sorted(a))
	print(*sorted(b))


for _ in range(int(input())):
	N = int(input())
	a = []
	b = []
	o = True
	if N % 4 != 0:
		print('NO')
		continue
	for i in range(N // 2):
		if o:
			a += [N - i, i + 1]
			o = not o
		else:
			b += [N - i, i + 1]
			o = not o
	print('YES')
	print(*sorted(a))
	print(*sorted(b))


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


for i in range(int(input())):
	n = int(input())
	if n * (n + 1) // 2 % 2:
		print('NO')
		continue
	else:
		print('YES')
	(A, B) = ([], [])
	for i in range(1, n // 2 + 1):
		if i % 2 != 0:
			A.append(i)
			B.append(i + n // 2)
		else:
			A.append(i + n // 2)
			B.append(i)
	A.sort()
	B.sort()
	print(*A)
	print(*B)


case = int(input())
for _ in range(case):
	n = int(input())
	if n * (n + 1) // 2 % 2 != 0:
		print('NO')
		continue
	print('YES')
	A = []
	B = []
	for i in range(1, n // 2 + 1):
		if i % 2 != 0:
			A.append(i)
			B.append(i + n // 2)
		else:
			A.append(i + n // 2)
			B.append(i)
	A.sort()
	B.sort()
	for value in A:
		print(value, end=' ')
	print()
	for value in B:
		print(value, end=' ')
	print()


t = input()
for c in range(0, int(t)):
	n = int(input())
	if n % 4 == 0:
		a = []
		for i in range(n):
			a.append(i + 1)
		a1 = []
		a2 = []
		for j in range(int(n / 4)):
			a1.append(a[2 * j])
			a1.append(a[n - 1 - 2 * j])
			a2.append(a[2 * j + 1])
			a2.append(a[n - 2 - 2 * j])
		a3 = sorted(a1)
		a4 = sorted(a2)
		print('YES')
		print(*a3)
		print(*a4)
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = [int(c) for c in range(1, n + 1)]
	if n * (n + 1) / 2 % 2 == 0:
		print('YES')
		intr = int(n / 4)
		l1 = l[:intr] + l[n - intr:]
		l2 = l[intr:n - intr]
		print(*l1)
		print(*l2)
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	if n % 4 == 0:
		print('YES')
		l1 = list(range(1, n // 4 + 1)) + list(range(n - n // 4 + 1, n + 1))
		l2 = list(range(n // 4 + 1, n // 2 + 1)) + list(range(n // 2 + 1, n - n // 4 + 1))
		for j in l1:
			print(j, ' ', end='')
		print()
		for j in l2:
			print(j, ' ', end='')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	(a, b) = ([], [])
	if n % 4 == 0:
		print('YES')
		for i in range(n // 4):
			a.append(i + 1)
			a.append(3 * n // 4 + i + 1)
		for i in range(n // 2):
			b.append(n // 4 + i + 1)
		a.sort()
		print(*a)
		print(*b)
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = [int(e) for e in range(1, n + 1)]
	a = []
	b = []
	if n % 4 != 0:
		print('NO')
	else:
		print('YES')
		for e in range(n):
			if e < n // 4 or e >= n // 4 + n // 2:
				a.append(l[e])
			else:
				b.append(l[e])
		print(' '.join(map(str, a)))
		print(' '.join(map(str, b)))


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


t = int(input())
while t != 0:
	n = int(input())
	if n % 4 == 0:
		print('YES')
		a1 = []
		a2 = []
		a = [i for i in range(1, n + 1)]
		i = 0
		j = n - 1
		c = 0
		while i < j:
			if c % 2 == 0:
				a1.append(a[i])
				a1.append(a[j])
			else:
				a2.append(a[i])
				a2.append(a[j])
			i += 1
			j -= 1
			c += 1
		for i in range(1, len(a1) - 1):
			(a1[i], a1[i + 1]) = (a1[i + 1], a1[i])
		print(*a1)
		print(*a2)
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	if n % 4 != 0:
		print('NO')
		continue
	else:
		for i in range(n // 4):
			a.append(i + 1)
		for i in range(n // 4):
			a.append(n - n // 4 + i + 1)
		for i in range(n // 2):
			b.append(n // 4 + i + 1)
	print('YES')
	a_to_str = ' '.join([str(elem) for elem in a])
	b_to_str = ' '.join([str(elem) for elem in b])
	print(a_to_str)
	print(b_to_str)


t = int(input())
for _ in range(t):
	n = int(input())
	a = ''
	b = ''
	if n % 4 == 0:
		for i in range(int(n / 4)):
			a = a + str(4 * i + 1) + ' '
			b = b + str(4 * i + 2) + ' '
		for i in range(int(n / 4)):
			a = a + str(4 * i + 4) + ' '
			b = b + str(4 * i + 3) + ' '
		print('YES')
		print(a)
		print(b)
	else:
		print('NO')


tests = int(input())
for i in range(tests):
	n = int(input())
	total = n * (n + 1) // 2
	if n & 1 or total & 1:
		print('NO')
	else:
		arr = [i for i in range(1, n + 1)]
		half = n // 2
		arr1 = arr[:half // 2] + arr[-half // 2:]
		arr2 = arr[half // 2:-half // 2]
		print('YES')
		print(*arr1[::-1])
		print(*arr2)


T = int(input())
for x in range(T):
	n = int(input())
	if n % 4 != 0:
		print('NO')
	else:
		print('YES')
		p = []
		q = []
		for i in range(n // 4):
			p.append(1 + 2 * i)
			q.append(2 + 2 * i)
		for i in range(n // 4):
			p.append(n // 2 + 2 + 2 * i)
			q.append(n // 2 + 1 + 2 * i)
		print(*p)
		print(*q)


def prefix_sum(n):
	if n % 4 != 0:
		print('NO')
	else:
		a = list()
		b = list()
		for i in range(1, n + 1):
			if i <= n // 4 or i > 3 * n // 4:
				a.append(i)
			else:
				b.append(i)
		print('YES')
		print(*a)
		print(*b)
t = int(input())
for _ in range(t):
	n = int(input())
	prefix_sum(n)


t = int(input())
for _ in range(t):
	n = int(input())
	if n <= 2:
		print('NO')
	elif n * (n + 1) / 2 % 2 != 0:
		print('NO')
	else:
		a = []
		b = []
		flag = True
		for num in range(1, n // 2 + 1):
			if num == n // 2 and num % 2 != 0:
				a.append(num)
				b.append(num + 1)
				break
			if flag:
				a.append(num)
				a.append(n - num + 1)
			else:
				b.append(num)
				b.append(n - num + 1)
			flag = not flag
		a.sort()
		b.sort()
		print('YES')
		print(*a)
		print(*b)


m = int(input())
for _ in range(m):
	n = int(input())
	if n % 4 != 0:
		print('NO')
	else:
		print('YES')
		l = []
		l1 = []
		i = 1
		j = n
		while i < j:
			l.append(i)
			l.append(j)
			i += 1
			j -= 1
			l1.append(i)
			l1.append(j)
			i += 1
			j -= 1
		l.sort()
		l1.sort()
		print(*l)
		print(*l1)


T = int(input())
for i in range(0, T):
	a = int(input())
	ff = []
	ss = []
	if a % 4 == 0:
		print('YES')
		for j in range(1, a + 1, 4):
			ff.append(str(j))
			ff.append(str(j + 3))
			ss.append(str(j + 1))
			ss.append(str(j + 2))
		sf = ''
		fs = ''
		for j in range(0, a // 2):
			if j % 2 == 0:
				sf += ff[j] + ' '
				fs += ss[j] + ' '
		for j in range(0, a // 2):
			if j % 2 == 1:
				sf += ff[j] + ' '
				fs += ss[j] + ' '
		print(sf)
		print(fs)
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	if N & 2:
		print('NO')
		continue
	print('YES')
	print(*range(1, (N >> 1) + 1, 2), *range((N >> 1) + 2, N + 1, 2))
	print(*range(2, (N >> 1) + 1, 2), *range((N >> 1) + 1, N + 1, 2))


import sys
import math
import bisect
from sys import stdin, stdout
from itertools import accumulate, chain, combinations, groupby, permutations, product
from collections import deque, Counter
from bisect import bisect_left, bisect_right
from math import gcd, sqrt, sin, cos, tan, degrees, radians
from fractions import Fraction
from decimal import Decimal
import sys
MOD = 10 ** 9 + 7
INF = 10 ** 20
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

def solve():
	n = int(input())
	if n % 4 != 0:
		print('NO')
	else:
		print('YES')
		p = []
		q = []
		for i in range(n // 4):
			p.append(1 + 2 * i)
			q.append(2 + 2 * i)
		for i in range(n // 4):
			p.append(n // 2 + 2 + 2 * i)
			q.append(n // 2 + 1 + 2 * i)
		print(*p)
		print(*q)
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	b = []
	if n * (n - 1) // 2 % 2 == 0:
		for j in range(1, n // 2 + 1):
			if j % 2 == 0:
				b.append(j)
			else:
				a.append(j)
		for k in range(n // 2 + 1, n + 1):
			if k % 2 == 0:
				a.append(k)
			else:
				b.append(k)
		if sum(a) != sum(b) or n <= 2:
			print('NO')
		elif sum(a) == sum(b):
			print('YES')
			print(*a)
			print(*b)
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	for k in range(1, n // 2 + 1):
		if k % 2 != 0:
			a.append(k)
			a.append(n - (k - 1))
		else:
			b.append(k)
			b.append(n - (k - 1))
	if n // 2 % 2 == 0:
		print('YES')
		for i in sorted(a):
			print(i, end=' ')
		print()
		for j in sorted(b):
			print(j, end=' ')
		print()
	else:
		print('NO')


import math as m

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return abs(a)

def ncr(N, R):
	return m.factorial(N) // (m.factorial(R) * m.factorial(N - R))

def getL():
	return [int(i) for i in input().split(' ')]

def getInt():
	return int(input())

def solve():
	n = getInt()
	if n * (n + 1) // 2 % 2 == 0:
		print('YES')
		for i in range(1, n // 4 + 1):
			print(i, end=' ')
		for i in range(n - n // 4 + 1, n + 1):
			print(i, end=' ')
		print()
		for i in range(n // 4 + 1, n - n // 4 + 1):
			print(i, end=' ')
		print()
	else:
		print('NO')
for _ in range(getInt()):
	solve()


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


for _ in range(int(input())):
	n = int(input())
	if n % 4 != 0:
		print('NO')
		continue
	A = []
	B = []
	for i in range(1, int(n / 4) + 1):
		A.append(i)
	for i in range(int(n / 4) + 1, int(3 * n / 4) + 1):
		B.append(i)
	for i in range(int(3 * n / 4) + 1, n + 1):
		A.append(i)
	print('YES')
	print(' '.join(map(str, A)))
	print(' '.join(map(str, B)))


for i in range(int(input())):
	n = int(input())
	if n * (n + 1) // 2 % 2 != 0:
		print('NO')
	else:
		print('YES')
		print(*list(range(1, n // 4 + 1)) + list(range(n - n // 4 + 1, n + 1)))
		print(*list(range(n // 4 + 1, n - n // 4 + 1)))


t = int(input())
while t > 0:
	n = int(input())
	A = []
	B = []
	if n % 4 != 0:
		print('NO')
	else:
		for j in range(1, n // 4 + 1):
			A.append(j)
		for j in range(n // 4 + 1, 3 * n // 4 + 1):
			B.append(j)
		for j in range(3 * n // 4 + 1, n + 1):
			A.append(j)
		print('YES')
		print(*A, sep=' ')
		print(*B, sep=' ')
	t -= 1


for i in range(int(input())):
	n = int(input())
	l1 = []
	l2 = []
	if n % 4 == 0:
		print('YES')
		for i in range(1, n // 4 + 1):
			l1.extend([4 * i - 3, 4 * i])
			l2.extend([4 * i - 2, 4 * i - 1])
		(l1[0], l1[n // 2 - 1]) = (l1[n // 2 - 1], l1[0])
		(l2[0], l2[n // 2 - 1]) = (l2[n // 2 - 1], l2[0])
		print(*l1)
		print(*l2)
	else:
		print('NO')


def ans(n):
	if n % 4 != 0:
		return 'NO'
	else:
		arr1 = []
		arr2 = []
		i = 1
		j = 0
		while len(arr1) != n // 2:
			arr1.append(i)
			arr1.append(n - j)
			i += 1
			j += 1
		while len(arr2) != n // 2:
			arr2.append(i)
			arr2.append(n - j)
			i += 1
			j += 1
		arr1.sort()
		arr2.sort()
		print('YES')
		return [arr1, arr2]
test_cases = int(input())
while test_cases != 0:
	d = int(input())
	x = ans(d)
	if type(x) != str:
		for y in x:
			print(*y)
	else:
		print(x)
	test_cases -= 1