Đề bài

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 các 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 \geq B \geq 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_1, a_2, \dots, a_n~ là số kẹo của ~n~ gói, hãy tìm cách chia thỏa mãn để ~(A - C)~ đạt giá trị nhỏ nhất.

Input

• Dòng đầu chứa số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~a_i \leq 10^9~).

Output

• Ghi ra một dòng chứa một số là giá trị ~(A - C)~ nhỏ nhất tìm được.

Ví dụ

Sample Input 1

4
5 5 3 4

Sample Output 1

2

Giới hạn

• Thời gian: 2.0s
• Bộ nhớ: 256M

Subtasks

• Subtask 1: Có 25% số test có ~n = 3~.
• Subtask 2: Có 50% số test có ~n \leq 10~.
• Subtask 3: Có 25% số test còn lại có ~n \leq 50~ và tổng số kẹo trong ~n~ gói không vượt quá ~1000~.