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