Có một dãy các số nguyên a1, a2, ..., an. Ta chia dãy số này thành 2 dãy số 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à T1.
• 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à T2.

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 vào:

• Dòng đầu tiên ghi một số nguyên dương n (n <=1000000)
• Dòng thứ hai ghi n số nguyên a1, a2, ..., an với |a_i| <= 10⁵ (1 <= i <= n), mỗi số cách nhau một dấu cách.

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