2024042206 - 中心位置

辰辰看到一个包含 n 个元素的数组,于是想找一找它的中心位置,该位置定义如下:

是数组的一个下标,这个下标左边的元素的和等于右边的元素的和,则这是一个中心位置(不含它本身)。

请你帮助辰辰找到数组 A 的中心位置,如果有多个中心位置,输出最靠近左边的一个即可,如果不存在中心位置,输出 −1。

Input

第一行,一个整数n

第二行,数组A的n个元素

Output

一行,一个整数,表示数组 A 的中心位置。

Examples

Input

3
1 2 3

Output

-1

Input

6
1 7 3 6 5 6

Output

4

Input

5
1 0 1 -2 2

Output

2

Hint

对于50%的测试数据,1≤n≤1000

对于100%的测试数据,1≤n≤100000,-10000≤A[i]≤10000

Time Limit 1000 毫秒
Memory Limit 128 MB
Stats
上一题 下一题