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 3 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, j$. Tổng số chiếc kẹo của phần 2 là $y = A_{i+1} + A_{i+2} + \dots + A_j$;
• Phần 3 gồm các gói kẹo $j + 1, j + 2, \dots, N$. Tổng số chiếc kẹo của phần 3 là $z = A_{j+1} + A_{j+2} + \dots + A_N$;
• Với $1 \le i < j < 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 phần có tổng số kẹo nhiều nhất và phần có tổng số kẹo ít nhất là nhỏ nhất, tức là $max(x, y, z) - min(x, y, z)$ đạt giá trị nhỏ nhất. Ta đặt giá trị $T = max(x, y, z) - min(x, y, z)$.

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 200$;
• Có 25% số test ứng với 25% số điểm thỏa mãn $200 < N \le 2000$;
• Có 25% số test ứng với 25% số điểm thỏa mãn $2000 < N \le 2 \times 10^5$.