Cho mảng \(A\) gồm \(n\) phần tử nguyên. Hãy chia \(A\) thành \(2\) tập sao cho giá trị tuyệt đối của hiệu của tổng \(2\) tập là nhỏ nhất có thể.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai gồm nsố nguyên \(A_i\).

Output

• In ra hiệu nhỏ nhất có thể.

Điều kiện

• \(1 \le n \le 40\)
• \(|a_i|\le 10^{9}\)

Sample Input 1

3
1 2 4

Sample Output 1

1