Có một dãy các số nguyên ~a_1, a_2, ..., a_n~. Ta chia dãy số này thành 2 dãy con như sau:

• Dãy con thứ nhất gồm ~k~ số đầu tiên trong dãy đã cho và tổng các phần tử của dãy con này là ~T_1~.
• Dãy con thứ hai gồm các số còn lại của dãy số đã cho và tổng các phần tử của dãy con này là ~T_2~.

Yêu cầu: Tìm số nguyên dương ~k~ là độ dài của dãy con thứ nhất sao cho ~|T1 − T2|~ nhỏ nhất.

Chú ý: Nếu có hơn một số ~k~ thỏa mãn thì ghi ra số ~k~ nhỏ nhất.

Dữ liệu

• Dòng đầu tiên ghi một số nguyên dương ~n~ (~n \le 1000000~)
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, ..., a_n~ với ~|a_i| \le 10~ (~1 \le i \le n~), mỗi số cách nhau một dấu cách.

Kết quả

• Ghi ra một số nguyên dương ~k~ thỏa mãn yêu cầu của đề bài.

Sample Input

6
4 7 1 1 4 6

Sample Output

2

Nguồn: THT 2015