Chia kẹo

Có $N$ gói kẹo được đánh số hiệu từ 1 đến $N$. Gói kẹo thứ $i$ $(i = 1, 2, 3, \dots, N)$ có $A_i$ chiếc kẹo. Cần phân chia $N$ gói kẹo thành 2 phần:

• Phần 1 gồm các gói kẹo $1, 2, \dots, i$. Tổng số chiếc kẹo của phần 1 là $x = A_1 + A_2 + \dots + A_i$;
• Phần 2 gồm các gói kẹo $i + 1, i + 2, \dots, N$. Tổng số chiếc kẹo của phần 2 là $y = A_{i+1} + A_{i+2} + \dots + A_N$;
• Với $1 \le i < N$.

Yêu cầu: Tìm cách phân chia $N$ gói kẹo sao cho chênh lệch giữa số kẹo của hai phần là nhỏ nhất, tức là $|x - y|$ đạt giá trị nhỏ nhất. Ta đặt giá trị $T = |x - y|$.

Dữ liệu cho trong tệp văn bản ChiaKeo.Inp gồm:

• Dòng thứ nhất ghi số nguyên dương $N$ là số gói kẹo.
• Dòng thứ hai ghi $N$ số nguyên dương $A_1, A_2, \dots, A_N$ $(1 \le A_i \le 10^3)$ là số chiếc kẹo của $N$ gói kẹo.

Các số ghi trên một dòng cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản ChiaKeo.Out là giá trị nhỏ nhất của $T$.

• Có 50% số test ứng với 50% số điểm thỏa mãn $3 \le N \le 1000$;
• Có 50% số test ứng với 50% số điểm thỏa mãn $1000 < N \le 10^5$.