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.

见题面

见题面