Cho một dãy số nguyên \(a\) gồm \(n\) phần tử. Một vị trí \(i\) được gọi là điểm cân bằng nếu tổng các phần tử nằm bên trái vị trí \(i\) bằng đúng tổng các phần tử nằm bên phải vị trí \(i\).

Yêu cầu: Hãy tìm chỉ số \(i\) nhỏ nhất thỏa mãn là điểm cân bằng của dãy. Nếu không có điểm cân bằng nào, in ra \(-1\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(-10^9 \le a_i \le 10^9\)), các số cách nhau bởi một khoảng trắng.

Output

• Ghi ra một số nguyên duy nhất là chỉ số cân bằng nhỏ nhất tìm được, hoặc in ra \(-1\) nếu không tồn tại.

Example

7
-7 1 5 2 -4 3 0

4

Constraints

• Có \(60\%\) số test tương ứng với \(n \le 10^3\).
• Có \(40\%\) số test còn lại không có ràng buộc gì thêm (\(n \le 10^6\)).