Andrew and Stones

Description:

Input:

The input contains several test cases. The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.

The first line for each test case contains one integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the length of the array.

The second line contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the array elements.

It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output:

For each test case print the minimum number of operations needed to move stones to piles $$$1$$$ and $$$n$$$, or print $$$-1$$$ if it's impossible.

Sample Input:

4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2

Sample Output:

4
-1
1
-1 

Note:

In the first test case, it is optimal to do the following:

1. Select $$$(i, j, k) = (1, 2, 5)$$$. The array becomes equal to $$$[2, 0, 2, 3, 7]$$$.
2. Select $$$(i, j, k) = (1, 3, 4)$$$. The array becomes equal to $$$[3, 0, 0, 4, 7]$$$.
3. Twice select $$$(i, j, k) = (1, 4, 5)$$$. The array becomes equal to $$$[5, 0, 0, 0, 9]$$$. This array satisfy the statement, because every stone is moved to piles $$$1$$$ and $$$5$$$.

There are $$$4$$$ operations in total.

In the second test case, it's impossible to put all stones into piles with numbers $$$1$$$ and $$$3$$$:

1. At the beginning there's only one possible operation with $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 1, 2]$$$.
2. Now there is no possible operation and the array doesn't satisfy the statement, so the answer is $$$-1$$$.

In the third test case, it's optimal to do the following:

1. Select $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 0, 2]$$$. This array satisfies the statement, because every stone is moved to piles $$$1$$$ and $$$3$$$.

The is $$$1$$$ operation in total.

In the fourth test case, it's impossible to do any operation, and the array doesn't satisfy the statement, so the answer is $$$-1$$$.