Có \(n\) gói kẹo được đánh số từ 1 đến \(n\), gói kẹo thứ \(i\) có \(a_i\) viên.

Yêu cầu: Hãy chia n gói kẹo cho hai em nhỏ (không bóc gói kẹo ra) sao cho chênh lệch tổng số kẹo của hai em là nhỏ nhất có thể.

Input

• Dòng thứ nhất chứa số nguyên \(n (2≤n≤10^4).\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (0≤a_i≤10^9 ).\)

Output

• In ra kết chênh lệch tổng kẹo của hai em nhỏ nhất tìm được.

Ràng buộc

• Subtask 1: 25% số điểm với \(n≤20.\)

• Subtask 2: 25% số điểm với \(n≤1000\), tổng số kẹo trong tất cả các gói \(≤ 3×10^4 \)

• Subtask 3: 25% số điểm với \(n≤40\).

• Subtask 4: 25% số điểm với \(n≤10^4\), tổng số kẹo trong tất cả các gói \(≤12×10^5.\)

Sample Input

5
19 17 13 9 7

Sample Output

1