Ba anh em An, Bình, Cường có n gói kẹo, gói thứ I có a_i cái kẹo. Cả ba quyết định chia n gói kẹo thành ba phần theo nguyên tắc:

• Không bóc các gói kẹo;
• Chia các gói kẹo thành ba phần, gọi A ≥ B ≥ C là số kẹo tương ứng của ba phần, khi đó An sẽ nhận phần có A cái kẹo, Bình sẽ nhận phần có B cái kẹo, Cường sẽ nhận phần có C cái kẹo.

Cách chia để cả ba anh em vui nhất là cách chia có giá trị (A – C) nhỏ nhất.

Yêu cầu: Cho a₁, a₂, …, a_n là số kẹo của n gói kẹo, hãy tìm cách chia thỏa mãn để (A – C) đạt giá trị nhỏ nhất.

Dữ liệu: Vào tử thiết bị vào chuẩn:

• Dòng đầu chứa số nguyên n;
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁹) là số kẹo của n gói kẹo.

Kết quả: Ghi ra thiết bị ra chuẩn một dòng chứa một số là giá trị (A – C) nhỏ nhất tìm được.

Ràng buộc:

• Có 15% số lượng test ứng với 15% số điểm có n = 3;
• Có 35% số lượng test khác ứng với 35% số điểm có n ≤ 10;
• Có 25% số lượng test khác ứng với 25% số điểm có n ≤ 20;
• Có 25% số lượng test còn lại ứng với 25% số điểm có n ≤ 100 và tổng số kẹo trong n gói không vượt quá 1000.

Ví dụ: