Find the Pivot Index

You are given an array of integers. The pivot index is defined as the smallest index (i) such that the sum of the elements to the left of (i) is equal to the sum of the elements to the right of (i). Formally, if we denote the elements by (a_0, a_1, \ldots, a_{n-1}), the pivot index (i) satisfies:

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

If no such index exists, output (-1).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) denoting the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output a single integer to standard output (stdout): the pivot index if it exists, otherwise (-1).## sample

6
1 7 3 6 5 6

3