37. Pivot Element of an Array

Difficulty: easy · Array, Prefix Sum

Problem

The **pivot index** of an array is an index `i` such that the sum of all elements strictly to the left of `i` equals the sum of all elements strictly to the right of `i`. (An empty side has sum 0.) The array is given on a single line without its size. Print the smallest pivot index (0-based), or `-1` if there is none.

Input

A single line containing one or more integers separated by single spaces.

Output

Print the smallest pivot index, or `-1`.

Example 1

Input:
1 7 3 6 5 6
Output:
3

Explanation: At index 3: the left side 1+7+3 = 11 and the right side 5+6 = 11.

Example 2

Input:
1 2 3
Output:
-1

Explanation: No index has equal sums on both sides, so -1.

Example 3

Input:
2 1 -1
Output:
0

Explanation: At index 0 the left sum is 0 (empty) and the right sum is 1 + (-1) = 0.

Constraints

- 1 <= number of integers <= 10^5 - -10^4 <= each integer <= 10^4

Solutions are judged against 3 sample and 8 hidden tests. Sign in to solve it · All problems