Balance The Array

ArrayGreedyPrefix Sum

Given an array of integers, your task is to balance the array so that the sum of the first half is equal to the sum of the second half by possibly removing exactly one element. Return the index of the element that can be removed to achieve this balance, or return -1 if it's not possible to balance the array by removing one element.

Example 1

Input

Output

Explanation. Removing the element at index 4 gives arrays [1,2,3,4] and []. The sums of both halves are 10.

Example 2

Input

Output

Explanation. Removing the element at index 0 gives arrays [3,1,2,1] and [5]. The sum of the first half is 7 and the sum of the second half is also 7.

Example 3

Input

Output

Explanation. Removing the element at index 2 gives arrays [3,3] and [3]. Both halves have equals sums of 6.

Example 4

Input

Output

-1

Explanation. There is no possible way to balance the array by removing exactly one element.

Follow-up: Can you solve this problem in linear time, O(n)?

Constraints:

The array will contain at least two elements and all elements are integers. All integer values will fit within the standard 32-bit signed integer range.

Views: 3