D. Evenly Separable
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an integer array $$$b$$$ of $$$n$$$ positive integers. For any non-negative integer $$$x$$$, define a new array $$$a$$$ by $$$a_i := b_i + x$$$ for every $$$1\le i\le n$$$.

An array $$$a$$$ is called separable if and only if there exists an index $$$i$$$ with $$$1\le i \lt n$$$ such that $$$$$$a_1+a_2+\cdots+a_i = a_{i+1}+a_{i+2}+\cdots+a_n.$$$$$$

For each test case, find the minimum non-negative integer $$$x$$$ such that the array obtained after adding $$$x$$$ to every element of $$$b$$$ is separable. If no such $$$x$$$ exists, output $$$-1$$$ instead.

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 each test case contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$-10^9\le b_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 a single integer — the minimum non-negative integer $$$x$$$ such that the array $$$[b_1+x, b_2+x, \ldots, b_n+x]$$$ is separable. It can proven that under the constraints of this problem, if such integer exists, then it's never greater than $$$10^{18}$$$.

If no such integer exists, output $$$-1$$$.

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

In the first test case, the array is already separable because $$$ 1+2=3. $$$ Therefore, the minimum valid value is $$$x=0$$$.

In the second test case, after adding $$$x=3$$$, the array becomes $$$ [4,5,6,7,8]. $$$ Now $$$ 4+5+6 = 7+8 = 15, $$$ so the array is separable. No smaller non-negative value works.

In the third test case, after adding any $$$x$$$, the array becomes $$$ [1+x,2+x]. $$$ The two parts would have sums $$$1+x$$$ and $$$2+x$$$, which can never be equal, so the answer is $$$-1$$$.