Cho \(n\) gói kẹo được đánh số hiệu từ 1 đến \(n\). Gói kẹo thứ \(i\ (i = 1,2,3,\ldots,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,..,i\). Tổng số chiếc kẹo trong phần này là \(x = a_{1} + a_{2} + \ldots + a_{i}\);

• Phần 2 gồm các gói kẹo \(i + 1,\ i + 2,\ldots,j\). Tổng số chiếc kẹo trong phần này là \(y = a_{i + 1} + a_{i + 2} + \ldots + a_{j}\);

• Phần 3 gồm các gói kẹo \(j + 1,\ j + 2,\ldots,j + n\). Tổng số chiếc kẹo trong phần này là \(z = a_{j + 1} + a_{j + 2} + \ldots + a_{n}\);

• Với \(1 \leq i < j \leq 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 \(T = \max(x,y,z) - min(x,y,z)\).

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ \)là số lượng gói kẹo;

+ Dòng thứ hai ghi lần lượt \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{3})\).

Kết quả:

+ Ghi một số nguyên duy nhất cho biết giá trị nhỏ nhất của \(T\).

Ví dụ:

Ràng buộc:

+ Có 50% số test tương ứng 50% số điểm có \(3 \leq n \leq 200\);

+ Có \(25\%\) số test tương ứng 25% số điểm có \(200 < n \leq 2000\);

+ Có 25% số test còn lại tương ứng 25% số điểm có \(2000 < n \leq 2 \times 10^{5}\).