Few years back IUT(International University Of Technology) authority decided to increase the number of students. As more students are getting admitted every year but the number of classroom didn't increase, the classrooms became overpopulated. As people are complaining about this, and making new classrooms is not possible in next few years one of the very intelligent person of the authority gave an idea to tackle this situation. It is that, they will not increase the classrooms rather they will distribute the classes into rooms such a way that it doesn't look like overpopulated although all the students come out of the class at the same time. So, It'll create an illution amongst the visitor and they will think IUT is great as before.

The distribution process  is that for every class this class will either contain more students than all the adjacent classes or contain less students than the adjacent classes. All the classes are situated in a line , so each class has two adjacent classroom except the 1st and the last classroom.

suppose there are n classroom and the number of students of that classrooms are   a₁ , a₂ , a₃ , a₄ .......... ... a_N

You'll have to distribute the classes as

• a₁ > a₂ < a₃ > a₄ < ... a_{N or}
• a₁ < a₂ > a₃ < a₄ > ... a_N

However you can only do one type of operation. You can swap the classrooms at position i and n-i+1.

You'll have to determine the mimimum number of operations to distrubute the classrooms and make IUT great again. If it's impossible print -1

Input

First line of the input contains t, number of testcases,

Then each testcase takes a integer n, number of rooms and then n integers the population of n'th class.

1<t<10

0<n<10⁵

0<a_i<10⁹

Output

For each testcase on separate line print the minimum number of operations or -1 if not possible

Example

Input:

2

6

1 2 3 4 5 6

5

5 2 4 3 5

Output:

1

0