Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are a citizen of Arrayland. Your President (Mr. P) has given you a mundane problem:

You're given an array a with size N (1-based indexing). You are allowed to perform an arbitrary number (including zero) of operations of the following type: choose an integer i (1 ≤ i ≤ N) and swap a_{i} with a_{N-i+1}.

Your goal is to make the array a great. An array is great if it satisfies one of the following conditions:

a_{1} > a_{2} < a_{3} > a_{4} < ... a_{N}
a_{1} < a_{2} > a_{3} < a_{4} > ... a_{N}

Compute the minimum number of operations necessary to make the array a great or determine that it's impossible to make it great.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of the array a.
The second line contains N space-separated integers a_{1}, a_{2}, ..., a_{N}.

------ Output ------ 

Print a single line containing one integer — the minimum number of operations required to make the array great, or -1 if it's impossible.

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

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{5}$
$1 ≤ a_{i} ≤ 10^{9} for each valid i$

----- Sample Input 1 ------ 
1
6
1 2 3 4 5 6
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
Example case 1: The given array is NOT great. If you swap the second and the fifth element, then the array becomes great.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming


Solutions:
def swap(a, i):
	j = n - i - 1
	tmp = a[i]
	a[i] = a[j]
	a[j] = tmp
q = int(input())
for i in range(q):
	n = int(input())
	a = [int(t) for t in input().split()]
	ans = []
	ans.append([0, 0, 0, 0])
	mid = n // 2
	flag = True
	if n == 2 and a[0] == a[1]:
		flag = False
	for k in range(1, mid + 1):
		tmp = []
		l = mid - k
		if n % 2 == 0:
			r = mid + k - 1
		else:
			r = mid + k
		if k == 1 and n % 2 == 0:
			if a[l] > a[r]:
				ans.append([0, -1, -1, 1])
			elif a[l] < a[r]:
				ans.append([-1, 1, 0, -1])
			else:
				flag = False
				break
			continue
		if n % 2 == 0:
			curr = -1
			if a[l] > a[l + 1] and a[r - 1] > a[r] and (ans[k - 1][2] >= 0):
				curr = ans[k - 1][2]
			if a[l] > a[r - 1] and a[l + 1] > a[r] and (ans[k - 1][3] >= 0):
				if ans[k - 1][3] < curr or curr == -1:
					curr = ans[k - 1][3]
			tmp.append(curr)
			curr = -1
			if a[r] > a[l + 1] and a[r - 1] > a[l] and (ans[k - 1][2] >= 0):
				curr = ans[k - 1][2] + 1
			if a[r] > a[r - 1] and a[l + 1] > a[l] and (ans[k - 1][3] >= 0):
				if ans[k - 1][3] + 1 < curr or curr == -1:
					curr = ans[k - 1][3] + 1
			tmp.append(curr)
			curr = -1
			if a[l] < a[l + 1] and a[r - 1] < a[r] and (ans[k - 1][0] >= 0):
				curr = ans[k - 1][0]
			if a[l] < a[r - 1] and a[l + 1] < a[r] and (ans[k - 1][1] >= 0):
				if ans[k - 1][1] < curr or curr == -1:
					curr = ans[k - 1][1]
			tmp.append(curr)
			curr = -1
			if a[r] < a[l + 1] and a[r - 1] < a[l] and (ans[k - 1][0] >= 0):
				curr = ans[k - 1][0] + 1
			if a[r] < a[r - 1] and a[l + 1] < a[l] and (ans[k - 1][1] >= 0):
				if ans[k - 1][1] + 1 < curr or curr == -1:
					curr = ans[k - 1][1] + 1
			tmp.append(curr)
		if n % 2 == 1:
			curr = -1
			if a[l] > a[l + 1] and a[r - 1] < a[r] and (ans[k - 1][2] >= 0):
				curr = ans[k - 1][2]
			if a[l] > a[r - 1] and a[l + 1] < a[r] and (ans[k - 1][3] >= 0):
				if ans[k - 1][3] < curr or curr == -1:
					curr = ans[k - 1][3]
			tmp.append(curr)
			curr = -1
			if a[r] > a[l + 1] and a[r - 1] < a[l] and (ans[k - 1][2] >= 0):
				curr = ans[k - 1][2] + 1
			if a[r] > a[r - 1] and a[l + 1] < a[l] and (ans[k - 1][3] >= 0):
				if ans[k - 1][3] + 1 < curr or curr == -1:
					curr = ans[k - 1][3] + 1
			tmp.append(curr)
			curr = -1
			if a[l] < a[l + 1] and a[r - 1] > a[r] and (ans[k - 1][0] >= 0):
				curr = ans[k - 1][0]
			if a[l] < a[r - 1] and a[l + 1] > a[r] and (ans[k - 1][1] >= 0):
				if ans[k - 1][1] < curr or curr == -1:
					curr = ans[k - 1][1]
			tmp.append(curr)
			curr = -1
			if a[r] < a[l + 1] and a[r - 1] > a[l] and (ans[k - 1][0] >= 0):
				curr = ans[k - 1][0] + 1
			if a[r] < a[r - 1] and a[l + 1] > a[l] and (ans[k - 1][1] >= 0):
				if ans[k - 1][1] + 1 < curr or curr == -1:
					curr = ans[k - 1][1] + 1
			tmp.append(curr)
		ans.append(tmp)
	if not flag or max(ans[mid]) == -1:
		print(-1)
	else:
		print(min([x for x in ans[mid] if x >= 0]))