Tặng quà

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.

Từ tệp GIFT.INP gồm:

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

Đưa ra tệp 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.

• Các test tương ứng với 50% số điểm có $n \le 10^2, A_i \le 10^3$
• Các test tương ứng với 50% số điểm $n \le 10^4, A_i \le 10^5$.