Cho \(n\) quả táo, quả thứ \(i\) có khối lượng là \(p_i\). Bạn hãy viết chương trình chia \(n\) quả táo này vào hai túi khác nhau sao cho chênh lệch khối lượng táo giữa hai túi là thấp nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \(\left(1 \leq n \leq 20\right)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(p_1\), \(p_2\),..., \(p_n\). \(\left(1\le p_i\le 10^9\right)\)

Output

• In ra chênh lệch nhỏ nhất tìm được.

Ví dụ

Sample input 01

5
3 2 7 4 1

Sample output 01

1