Câu 4. (100 điểm) CHIA DÃY

Cho dãy gồm n số nguyên a₁, a₂, ..., a_n. Ta chia dãy số đã cho thành 2 dãy con như sau:

+ Dãy con thứ nhất gồm k số đầu tiên (1<=  k<= n); tổng các số 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à  có tổng là T2.

Yêu cầu: Tìm số nguyên dương k nhỏ nhất sao cho |T1-T2| nhỏ nhất.

Dữ liệu vào: File CHIADAY.INP có cấu trúc như sau:

- Dòng đầu tiên ghi một số nguyên dương n (n <=10⁶).

- Dòng thứ hai ghi n số nguyên a₁, a₂, ..., a_n (|a_i|≤ 10⁹), mỗi số cách nhau một khoảng trắng.

Dữ liệu ra: Ghi ra file CHIADAY.OUT số nguyên dương k.

Ví dụ:

Giới hạn dữ liệu: Trong bộ test của bài sẽ có  60% test với 0< n, a_i <=10³.