Balance point

Problem

Print the first index i where the sum of the items before i equals the sum of the items after i. An empty side has sum 0. Print -1 when there is no such index.

Input, output and limits

Input: The first line has n. The second line has n integers.
Output: One integer.
Constraints: 1 ≤ n ≤ 100000
-1000 ≤ each item ≤ 1000

Examples

Example

Input

5
2 4 9 3 3

Output

Left sum 6, right sum 6 at index 2.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Keep a running sum of everything to the left.

Hint 2

The right sum is the total minus the left sum minus the current item.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Pair that fits a budgeteasy
Same letterseasy
First repeated ideasy
Group the anagramsmedium
Repeated order ideasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sums & Hashing problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sums & Hashing problems