Cho số nguyên dương ~ n ~ và dãy số nguyên ~ a_1,a_2,…,a_n ~. Hãy tìm vị trí ~ k ~ ~ (1 ≤ k < n) ~ sao cho tổng các số từ vị trí 1 đến ~ k ~ và tổng các số từ vị trí ~ k + 1 ~ đến ~ n ~ chênh lệch nhau là ít nhất. Nếu có nhiều hơn 1 vị trí thì chọn vị trí nhỏ nhất.

Dữ liệu vào

• Dòng đầu số nguyên ~ n ~ ~ (1≤n≤10^6) ~
• Dòng thứ 2 ghi ~ n ~ số nguyên ~ a_1,a_2,…,a_n ~ ~ (|a_i |≤1000) ~, mỗi số cách nhau một dấu cách.

Kết quả

• Số ~ k ~ thỏa điều kiện bài toán.

Ví dụ:

Input 1

5
1 2 3 4 5 

Output 1

3