Có một dãy các số nguyên a₁, a₂, ..., 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₁.
• 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₂.

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₁-T₂| 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: File văn bản CHIADAY.INP có cấu trúc như sau:

– 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 a₁, a₂, ..., a_n 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 file văn bản CHIADAY.OUT một số nguyên dương k thỏa mãn yêu cầu của đề bài.

Ví dụ: