Write Java Code

You have been given an integer array arr. Find the index in the array which satisfies the two conditions given below 1. The prefix sum must be equal to suffix sum (let us call it as 's') at that index 2. The value of 's' must be the highest (the prefix sum = suffix sum must be the highest in the array at that index) Input In the first line you would be given the size of the array arr which is 'n' In the second line there would be space separated integers which are contents of the array arr. Output The prefix sum which is the suffix sum which is also the highest in the array.

Input

8

-2 5 3 1 2 6 -4 2

Output

7