Cho dãy gồm \(n\) số nguyên \(a_{1},\ a_{2},\ ...,\ 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 \leq k < n)\); tổng các số 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à có tổng là \(T_{2}\).

Yêu cầu: Tìm số nguyên dương \(k\) nhỏ nhất sao cho \(|T_{1} - T_{2}|\) nhỏ nhất.

Dữ liệu vào:

- Dòng đầu tiên ghi một số nguyên dương \(n\ (n \leq 10^{6})\).

- Dòng thứ hai ghi \(n\) số nguyên \(a_{1},\ a_{2},\ ...,\ a_{n}\) \((a_{i} \leq 10^{9},\ 1 \leq \ i \leq \ n)\), mỗi số cách nhau một khoảng trắng.

Dữ liệu ra:

• Ghi ra 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^{3}\).