The pivot index is an index i such that the sum of the elements strictly to the left of i equals the sum of the elements strictly to the right of i. Elements to the side of an empty range sum to 0.
Return the leftmost pivot index, or -1 if none exists.
Input format
Line 1: an integer n.
Line 2: n space-separated integers (present whenever n >= 1).
Output format
One line: the leftmost pivot index (0-based), or -1.
Constraints
- 1 <= n <= 100000
- -1000 <= each value <= 1000