Cho ~ n ~ ~ (n ≤ 100) ~gói kẹo. Gói thứ ~ i ~ có ~ a_i ~ viên kẹo. Cần chia các gói kẹo này cho 2 em bé sao cho tổng số viên kẹo mỗi em nhận được chênh lệch ít nhất. Mỗi em nhận nguyên gói. Không mở gói kẹo ra để chia lại.

Dữ liệu vào

• Dòng dầu tiên ghi số nguyên dương ~ n ~
• Dòng thứ 2 ghi ~ n ~ số nguyên lần lượt là ~ a_1,a_2,…,a_n ~ ~ (1 ≤ a_i ≤ 100) ~

Kết quả

• Một số nguyên duy nhất là số kẹo chênh lệch ít nhất của hai em bé

Ví dụ:

Input 1

4
4 2 1 6 

Output 1

1