Find the Even Index

Given an array of integers, find an index i such that the sum of the integers to the left of i is equal to the sum of the integers to the right of i. If there exists such an index, output the smallest one; otherwise, output -1.

Note that the sum of an empty array is defined as 0. Thus, for a single element array, the left and right sums are both 0, so the answer is 0.

The condition can be written in LaTeX as follows:

$$\sum_{j=0}^{i-1} a_j = \sum_{j=i+1}^{n-1} a_j$$

inputFormat

The first line of input contains a single integer n (n ≥ 1) representing the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

For example:

7
1 2 3 4 3 2 1

outputFormat

Output a single integer which is the index where the sum of the numbers to the left equals the sum of the numbers on the right. If no such index exists, output -1.

For the sample input above, the output should be:

3

## sample

7
1 2 3 4 3 2 1

3