Equal Array
Tag(s):

## Algorithms, Dynamic Programming

Problem
Editorial
Analytics

You are given an array $A$ of size $N$

Find the minimum non negative number $X$ such that there exist an index $j$ and when you can replace $A_j$ by $A_j+X$, the sum of elements of array from index $1$ to $j$  and $j+1$ to  $N$ becomes equal, where $1 \le j \le N-1$. Assume array to be 1-indexed.

If there is no possible $X$ print $-1$ in separate line.

Input Format

The first line contains $T$, the number of test cases.
For each Test case :
The first line contains an integer $N$, size of the array.
The second line contains $N$ space-separated integers, the $i^{th}$ of which is $A_i$.

Input Constraints

$1 \le T \le 10^{ 5}$
$2 \le N \le 10^{5}$
$0 \le A_i \le 10^{6}$
Sum of N all over testcases doesn't not exceed $10^{6}$.

Output Format

For each test case, print the required answer in separate line.

SAMPLE INPUT
1
5
1 2 3 2 1

SAMPLE OUTPUT
3

Explanation

Add $3$ to the $2^{nd}$index(1-indexing).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Dell Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Greedy Algorithms
• Algorithms > Graphs