Jame có ~ n ~ món quà, món quà thứ ~ i ~ có giá trị là ~ a_i ~. Jame muốn tặng ~ n ~ món quà này cho hai bạn sao cho độ chênh lệch giữa tổng giá trị các món quà mà mỗi bạn nhận được là nhỏ nhất.

Yêu cầu: Tìm độ chênh lệch nhỏ nhất giữa tổng giá trị các món quà mà mỗi bạn nhận được.

Dữ liệu vào:

• Dòng 1: Chứa số nguyên dương ~ n ~ là số món quà ~ (2≤n≤1000) ~.
• Dòng 2: Chứa ~ n ~ số nguyên dương ~ a_i (a_i≤1000) ~ là giá trị của món quà thứ ~ i ~.

Kết quả:

• Đưa độ chênh lệch nhỏ nhất giữa tổng giá trị các món quà mà mỗi bạn nhận được.

Ví dụ:

Input

7
6 25 41 10 35 27 16 

4