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 \(|T_1−T_2|\) 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.

Input

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

Output

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

Example

6
4 7 1 1 4 6 

2