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.

Input

Đọc từ file văn bản GIFT.inp gồm:

• Dòng thứ nhất chứa số nguyên dương ~N~ là số món quà (~N \ge 2~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, … , A_N~ là giá trị của các món quà.

Output

Ghi ra file văn bản GIFT.out độ 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.

Ràng buộc

• ~N \le 10^3~
• ~A_i \le 10^5~

Các test tương ứng:

• ~50%~ số điểm có ~N \le 10^2~, ~A_i \le 10^3~.
• ~50%~ số điểm còn lại có ~N \le 10^3~, ~A_i \le 10^5~.

Sample Input

7
6 25 41 10 35 27 16

Sample Output

4