Có ~n~ quả táo biết cân nặng của từng quả là ~a_1, a_2, \dots, a_n~.

Yêu cầu: Hãy chia những quả táo thành hai nhóm sao cho chênh lệch tổng cân nặng của chúng nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên ~n\ (1\leq n\leq 20)~: số lượng quả táo
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n\ (1\leq a_i\leq 10^9)~: cân nặng của từng quả táo.

Dữ liệu ra:

• In ra một số nguyên: chênh lệch cân nặng nhỏ nhất của hai nhóm.

Input:

5
3 2 7 4 1

Output:

1

Giải thích:

• Nhóm 1 có quả táo nặng 2, 3 và 4 (tổng cân nặng 9), nhóm 2 có quả táo nặng 1 và 7 (tổng cân nặng 8).