Balanced Sum

Without reordering the array, find the pivot whose left-side and right-side element sums are equal, and return its 0-based index; the pivot itself belongs to neither side. A solution is guaranteed to exist.

输入格式

The first line contains n, followed by n positive integers; full original bounds 3≤n≤100000, 1≤a[i]≤20000. The guarantee that a solution exists comes from the original statement.

输出格式

Output a single integer answer.

样例 1

输入：

5
1 2 3 4 6

输出：

3

样例 2

输入：

4
1 2 3 3

输出：

2

样例 3

输入：

3
7 1 7

输出：

1

样例说明

The outputs of the three public examples are, in order: 3; 2; 1. These answers have been checked by independent enumeration or direct simulation.