#202EasyPrefix Sums & Difference Arrays· Left Sum Equals Right Sum

Balanced Pivot Day

A shop tracks its daily profit or loss in an array `nums` (a loss is negative). The accountant wants to find a **pivot day**: a day where the total profit of all days before it equals the total profit of all days after it. The pivot day itself is not counted on either side. Return the smallest index that is a pivot day, or `-1` if there is none. The sum of an empty side is 0, so day 0 can be a pivot when every later day adds up to 0, and the last day can be a pivot when every earlier day adds up to 0.

Input format

`nums`: the daily profit or loss values.

Output format

The smallest pivot index, or -1.

Examples

Input: nums = [1, 7, 3, 6, 5, 6]

Output: 3

Before index 3 the sum is 1 + 7 + 3 = 11 and after it the sum is 5 + 6 = 11, so the answer is 3.

Input: nums = [1, 2, 3]

Output: -1

No day splits the totals evenly, so the answer is -1.

Input: nums = [2, 1, -1]

Output: 0

Left of index 0 there is nothing (sum 0) and the rest is 1 - 1 = 0, so index 0 is a pivot.

Constraints

1 <= nums.length <= 10^5
-1000 <= nums[i] <= 1000

#prefix-sums
#arrays
#running-total
#scan