D. Problem from Yuzhnouralsk
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$.

In one operation, you may choose an index $$$i$$$ ($$$2 \le i \le n$$$) and simultaneously perform the following actions:

  • add $$$a_i$$$ to $$$a_{i-1}$$$;
  • if $$$i \lt n$$$, add $$$a_i$$$ to $$$a_{i+1}$$$;
  • replace $$$a_i$$$ with $$$-a_i$$$.
In all three actions, the value of $$$a_i$$$ before the operation is used.

Determine whether it is possible, using some number of operations (possibly zero), to obtain an array in which all elements are nonnegative. If it is possible, find the minimum number of operations required.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

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

Output

For each test case, output one integer — the minimum number of operations after which all elements of the array will be nonnegative, or $$$-1$$$ if this is impossible.

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

In the first test case, one operation with $$$i = 2$$$ is enough: the array $$$[1, -1, 2]$$$ becomes $$$[0, 1, 1]$$$.

In the second test case, the only possible operation $$$i = 2$$$ gives the array $$$[2, -3]$$$, and applying it again returns the original array. It is impossible to obtain an array in which all elements are nonnegative.

In the third test case, one can perform operations with $$$i = 2, 3, 2, 4$$$: $$$[5, -3, -2, 4] \to [2, 3, -5, 4] \to [2, -2, 5, -1] \to [0, 2, 3, -1] \to [0, 2, 2, 1]$$$. It can be shown that the obtained number of operations is minimal.