Cho dãy ~A~ gồm ~N~ phần tử. Một chỉ số ~i~ thuộc ~[1..N]~ được gọi là chỉ số cân bằng nếu tại ~i~ chia dãy thành hai phần sao cho Tổng các phần tử có chỉ số bé hơn ~i~ bằng tổng các phần tử có chỉ số lớn hơn ~i~; Tức là:

~A[1]+A[2]+⋯+A[i-1]=A[i+1]+A[i+2]+⋯+A[N]~I

Input:

• Dòng đầu ghi số ~N (1<=N<=10^6)~
• Dòng tiếp theo ghi ~N~ số nguyên cách nhau bởi dấu cách

Output:

• Gồm một số nguyên ghi chỉ số cân bằng bé nhất tìm được. Nếu không tồn tại chỉ số cân bằng, ghi ~-1~;

Ví dụ:

Input

7
-7 1 5 2 -4 3 0

Output

4

Giải thích:

~4~ là chỉ số cân bằng vì ~A[1]+A[2]+A[3]=-7+1+5=-1=A[5]+A[6]+A[7]=-4+3+0=-1~; Ngoài ra ta có ~7~ là chỉ số cân bằng vì ~sum(A[1]..A[6])=0~