You have a permutation: an array $a = [a_1, a_2, \ldots, a_n]$ of distinct integers from $1$ to $n$. The length of the permutation $n$ is odd.

You need to sort the permutation in increasing order.

In one step, you can choose any prefix of the permutation with an odd length and reverse it. Formally, if $a = [a_1, a_2, \ldots, a_n]$, you can choose any odd integer $p$ between $1$ and $n$, inclusive, and set $a$ to $[a_p, a_{p-1}, \ldots, a_1, a_{p+1}, a_{p+2}, \ldots, a_n]$.

Find a way to sort $a$ using no more than $\frac{5n}{2}$ reversals of the above kind, or determine that such a way doesn't exist. The number of reversals doesn't have to be minimized.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 2021$; $n$ is odd) — the length of the permutation.

The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the permutation itself.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2021$.


-----Output-----

For each test case, if it's impossible to sort the given permutation in at most $\frac{5n}{2}$ reversals, print a single integer $-1$.

Otherwise, print an integer $m$ ($0 \le m \le \frac{5n}{2}$), denoting the number of reversals in your sequence of steps, followed by $m$ integers $p_i$ ($1 \le p_i \le n$; $p_i$ is odd), denoting the lengths of the prefixes of $a$ to be reversed, in chronological order.

Note that $m$ doesn't have to be minimized. If there are multiple answers, print any.


-----Examples-----

Input
3
3
1 2 3
5
3 4 5 2 1
3
2 1 3
Output
4
3 3 3 3
2
3 5
-1


-----Note-----

In the first test case, the permutation is already sorted. Any even number of reversals of the length $3$ prefix doesn't change that fact.

In the second test case, after reversing the prefix of length $3$ the permutation will change to $[5, 4, 3, 2, 1]$, and then after reversing the prefix of length $5$ the permutation will change to $[1, 2, 3, 4, 5]$.

In the third test case, it's impossible to sort the permutation.

Source: codeforces | Difficulty: HARD
Tags: Greedy algorithms

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline

def swap(s):
	for i in range(s // 2):
		(a[i], a[s - i - 1]) = (a[s - i - 1], a[i])
	p.append(s)
	return
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	for i in range(n):
		if not a[i] % 2 ^ i % 2:
			m = -1
			break
	if m == -1:
		print(m)
		continue
	p = []
	for i in range(n // 2):
		(x, y) = (a.index(2 * i + 1), a.index(2 * i + 2))
		if x > y:
			swap(x + 1)
			y = x + 1 - y - 1
			swap(y)
			x = y - 1
			swap(n - 2 * i)
			(x, y) = (n - 2 * i - x - 1, n - 2 * i - y - 1)
			swap(x + 1)
			swap(n - 2 * i)
		else:
			swap(x + 1)
			swap(y)
			swap(n - 2 * i)
			swap(n - y + 1 - 2 * i)
			swap(n - 2 * i)
	swap(n)
	m = len(p)
	print(m)
	print(*p)


t = int(input())
for tc in range(t):
	n = int(input())
	row = list(map(int, input().split()))
	rowsort = sorted(row)[::-1]
	permutable = True
	for i in range(n):
		if (i - row[i]) % 2 == 0:
			permutable = False
			break
	if not permutable:
		print(-1)
	else:
		ret = []
		for i in range(int(n / 2)):
			rowi = row.index(n - 2 * i)
			if rowi != 0:
				ret.append(rowi + 1)
				row = row[rowi::-1] + row[rowi + 1:]
			rowi = row.index(n - 2 * i - 1)
			if rowi != 1:
				ret.append(rowi)
				ret.append(rowi + 2)
				ret.append(3)
				row = [row[0], row[rowi], row[rowi + 1]] + row[1:rowi] + row[rowi + 2:]
			ret.append(n - 2 * i)
			row = row[n - 2 * i - 1::-1] + row[n - 2 * i:]
		print(len(ret))
		print(' '.join(list(map(str, ret))))


import sys
input = sys.stdin.readline

def main():
	n = int(input())
	alst = list(map(int, input().split()))
	pos = [-1] * n
	for (i, a) in enumerate(alst):
		a -= 1
		alst[i] -= 1
		if (a - i) % 2 == 1:
			print(-1)
			return
		pos[a] = i
	ans = []
	for i in range(n - 1, 0, -2):
		p = pos[i]
		ans.append(p + 1)
		for j in range(p // 2):
			(alst[j], alst[p - j]) = (alst[p - j], alst[j])
			(pos[alst[j]], pos[alst[p - j]]) = (pos[alst[p - j]], pos[alst[j]])
		p = pos[i - 1]
		ans.append(p)
		p -= 1
		for j in range(p // 2):
			(alst[j], alst[p - j]) = (alst[p - j], alst[j])
			(pos[alst[j]], pos[alst[p - j]]) = (pos[alst[p - j]], pos[alst[j]])
		ans.append(p + 3)
		p += 2
		for j in range(p // 2):
			(alst[j], alst[p - j]) = (alst[p - j], alst[j])
			(pos[alst[j]], pos[alst[p - j]]) = (pos[alst[p - j]], pos[alst[j]])
		p = 2
		ans.append(3)
		for j in range(p // 2):
			(alst[j], alst[p - j]) = (alst[p - j], alst[j])
			(pos[alst[j]], pos[alst[p - j]]) = (pos[alst[p - j]], pos[alst[j]])
		p = i
		ans.append(p + 1)
		for j in range(p // 2):
			(alst[j], alst[p - j]) = (alst[p - j], alst[j])
			(pos[alst[j]], pos[alst[p - j]]) = (pos[alst[p - j]], pos[alst[j]])
	print(len(ans))
	print(*ans)
for _ in range(int(input())):
	main()


import sys
input = lambda : sys.stdin.readline().rstrip()
from random import shuffle
T = int(input())
for _ in range(T):

	def calcI():
		for (i, a) in enumerate(A):
			I[a] = i

	def addans(i):
		ANS.append(i)
		A[:i] = A[:i][::-1]
		calcI()
	N = int(input())
	A = [int(a) - 1 for a in input().split()]
	I = [0] * N
	k = (N - 1) // 2
	ng = 0
	for (i, a) in enumerate(A):
		if (i ^ a) & 1:
			ng = 1
			break
	if ng:
		print(-1)
		continue
	calcI()
	ANS = []
	while k:
		r = 2 * k
		l = r - 1
		if I[r] == r and I[l] == l:
			k -= 1
			continue
		if I[r] == 0 and I[l] == 1:
			addans(r + 1)
			k -= 1
			continue
		if I[r] - I[l] == 1:
			addans(I[r] + 1)
			continue
		if I[l] - I[r] == 1:
			addans(I[l] + 2)
			continue
		if I[r] == 0:
			addans(I[l])
			continue
		if I[l] > I[r]:
			addans(I[r] + 1)
			continue
		addans(I[r] + 1)
	if not ANS:
		ANS = [3, 3]
	print(len(ANS))
	print(*ANS)


from sys import stdin, stdout
import heapq
from collections import defaultdict
import math
import bisect
import io, os

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def main():
	t = int(stdin.readline())
	for _ in range(t):
		n = int(stdin.readline())
		arr = list(map(int, stdin.readline().split()))
		is_ok = True
		for i in range(n):
			if arr[i] % 2 == i % 2:
				is_ok = False
				break
		if not is_ok:
			stdout.write('-1\n')
			continue
		ans = []
		for i in range(0, n - 2, 2):
			x = n - i
			y = n - i - 1
			pos_x = pos_y = 0
			for j in range(n - i):
				if arr[j] == x:
					pos_x = j
				if arr[j] == y:
					pos_y = j
				if pos_x and pos_y:
					break
			if abs(pos_x - pos_y) != 1:
				if pos_x != 0:
					ans.append(pos_x + 1)
					for k in range(pos_x // 2):
						(arr[k], arr[pos_x - k]) = (arr[pos_x - k], arr[k])
					if pos_y < pos_x:
						pos_y = pos_x - pos_y
					pos_x = 0
				ans.append(pos_y)
				for k in range(pos_y // 2):
					(arr[k], arr[pos_y - 1 - k]) = (arr[pos_y - 1 - k], arr[k])
				pos_x = pos_y - 1
			if pos_y > pos_x and pos_x != 0:
				ans.append(pos_y + 2)
				for k in range((pos_y + 1) // 2):
					(arr[k], arr[pos_y + 1 - k]) = (arr[pos_y + 1 - k], arr[k])
				pos_y = 1
				pos_x = 2
			if pos_x > pos_y and pos_x != n - i - 1:
				ans.append(pos_x + 1)
				for k in range(pos_x // 2):
					(arr[k], arr[pos_x - k]) = (arr[pos_x - k], arr[k])
				pos_y = pos_x - pos_y
				pos_x = 0
			if pos_x == 0:
				ans.append(n - i)
				for k in range((n - i) // 2):
					(arr[k], arr[n - i - k - 1]) = (arr[n - i - k - 1], arr[k])
		if len(ans):
			stdout.write(str(len(ans)) + '\n')
			stdout.write(' '.join([str(x) for x in ans]) + '\n')
		else:
			stdout.write('2\n3 3\n')
main()


for _ in range(int(input())):
	n = int(input())
	A = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		if i % 2 != A[i] % 2:
			print(-1)
			break
	else:
		ans = []

		def rev(x):
			A[1:x + 1] = A[1:x + 1][::-1]
			ans.append(x)
		for x in range(n, 1, -2):
			i = A.index(x)
			rev(i)
			j = A.index(x - 1)
			rev(j - 1)
			rev(j + 1)
			rev(3)
			rev(x)
		print(len(ans))
		print(*ans)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def reverse(p, L):
	n = len(p)
	return [p[L - i - 1] for i in range(L)] + [p[i] for i in range(L, n)]

def solve(n, p):
	res = []
	p = [p[i] - 1 for i in range(n)]
	for i in range(n):
		if (i - p[i]) % 2:
			return [-1]
	for i in range(n - 1, 0, -2):
		o_i = p.index(i)
		res.append(o_i + 1)
		p = reverse(p, o_i + 1)
		e_i = p.index(i - 1)
		res.append(e_i)
		p = reverse(p, e_i)
		o_i = p.index(i)
		res.append(o_i + 3)
		p = [p[o_i + 2 - j] for j in range(o_i + 3)] + [p[j] for j in range(o_i + 3, n)]
		res.append(3)
		p = [p[2], p[1], p[0]] + [p[j] for j in range(3, n)]
		res.append(i + 1)
		p = [p[i - j] for j in range(i + 1)] + [p[j] for j in range(i + 1, n)]
	assert p == [i for i in range(n)]
	return res
for _ in range(int(input())):
	n = int(input())
	p = li()
	res = solve(n, p)
	if res[0] == -1:
		print(-1)
	else:
		print(len(res))
		print(*res)


from sys import stdin, stdout

def solve(n, a_a):
	p_a = [-1] * n
	for i in range(n):
		a_a[i] -= 1
		p_a[a_a[i]] = i
		if a_a[i] % 2 != i % 2:
			return [-1]
	res = []
	for i in range(n // 2, 0, -1):
		cur = i * 2
		res.append(p_a[cur] + 1)
		reverse(a_a, p_a, p_a[cur])
		res.append(p_a[cur - 1])
		reverse(a_a, p_a, p_a[cur - 1] - 1)
		res.append(p_a[cur - 1] + 2)
		reverse(a_a, p_a, p_a[cur - 1] + 1)
		res.append(p_a[cur] + 1)
		reverse(a_a, p_a, p_a[cur])
		res.append(cur + 1)
		reverse(a_a, p_a, cur)
	return [len(res), res]

def reverse(a_a, p_a, i):
	l = 0
	r = i
	while l < r:
		swap(a_a, l, r)
		swap(p_a, a_a[l], a_a[r])
		l += 1
		r -= 1

def swap(a_a, i, j):
	tmp = a_a[i]
	a_a[i] = a_a[j]
	a_a[j] = tmp
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a_a = list(map(int, stdin.readline().split()))
	res = solve(n, a_a)
	stdout.write(str(res[0]) + '\n')
	if res[0] > 0:
		stdout.write(' '.join(map(str, res[1])) + '\n')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
print = lambda s: sys.stdout.write(str(s) + '\n')

def f(n, p):
	if n == 1:
		return []
	if p[-1] == n and p[-2] == n - 1:
		return f(n - 2, p[:-2])
	i = p.index(n)
	ans = []
	ans.append(i + 1)
	p[0:i + 1] = p[0:i + 1][::-1]
	goTo5 = False
	j = p.index(n - 1)
	if j == 1:
		goTo5 = True
	if not goTo5:
		ans.append(j)
		p[0:j] = p[0:j][::-1]
		ans.append(j + 2)
		p[0:j + 2] = p[0:j + 2][::-1]
		ans.append(3)
		p[0:3] = p[0:3][::-1]
	ans.append(n)
	p = p[::-1]
	return ans + f(n - 2, p[:-2])

def solve():
	n = int(input())
	p = list(map(int, input().split()))
	expectedOdd = list()
	actualOdd = list()
	for i in range(0, n, 2):
		if p[i] % 2 == 0:
			print(-1)
			return
	ans = list(f(n, p))
	print(len(ans))
	if ans:
		print(' '.join((str(x) for x in ans)))
for nt in range(int(input())):
	solve()


import random
tc = int(input())
while tc > 0:
	tc -= 1
	n = int(input())

	def gen():
		even = list(range(0, n, 2))
		odd = list(range(1, n, 2))
		random.shuffle(even)
		random.shuffle(odd)
		return [odd[i // 2] if i % 2 else even[i // 2] for i in range(n)]
	a = list(map(lambda x: int(x) - 1, input().split()))
	if any(((i + a[i]) % 2 for i in range(n))):
		print(-1)
	else:
		ans = []

		def rev(i):
			global a, ans
			assert i % 2 == 1 and i <= n
			a[:i] = a[i - 1::-1]
			ans += [i]
		for i in range(n - 2, -1, -2):
			while True:
				if a[i] == i and a[i + 1] == i + 1:
					break
				if a[0] == i + 1 and a[1] == i:
					rev(i + 2)
				elif abs(a.index(i) - a.index(i + 1)) == 1:
					rev(a.index(i) + 2)
				elif a[0] == i + 1:
					rev(a.index(i))
				else:
					rev(a.index(i + 1) + 1)
			assert all((j == a[j] for j in range(i, n)))
		print(len(ans))
		print(*ans)


import sys
import getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]

def solve_(arr):
	for (i, x) in enumerate(arr, start=1):
		if i % 2 != x % 2:
			return []
	res = []

	def flip(idx):
		if idx == 1:
			return
		nonlocal res
		nonlocal arr
		res.append(idx)
		arr = arr[:idx][::-1] + arr[idx:]
	for i in range(len(arr) // 2):
		right = len(arr) - i * 2
		k = len(arr) - i * 2
		log(right)
		idx = arr.index(k)
		flip(idx + 1)
		idx = arr.index(k - 1)
		flip(idx)
		flip(right)
		idx = arr.index(k)
		flip(idx + 1)
		flip(right)
	return res
for case_num in range(int(input())):
	k = int(input())
	arr = list(map(int, input().split()))
	res = solve(arr)
	if res == []:
		print(-1)
		continue
	print(len(res))
	res = ' '.join((str(x) for x in res))
	print(res)