Sau kì thi tin học trẻ, shiba đã đặt mua \(N\) gói kẹo nhằm tự thưởng cho mình, và cũng để chia sẻ với _minhduc. Số kẹo lần lượt trong mỗi gói là \(a_1,a_2,a_3,\ldots,a_n\). shiba muốn chia các gói kẹo này thành hai phần, một phần đưa cho _minhduc, một phần để mình ăn. Để cho _minhduc khỏi ganh tị, shiba muốn tìm cách chia mà chênh lệch tổng số kẹo của hai người là nhỏ nhất. Vì các gói kẹo có hương vị khác nhau, shiba không muốn bóc các gói kẹo để tránh chúng bị trộn lẫn..

Yêu cầu: Hãy giúp shiba tìm cách chia các gói kẹo sao cho chênh lệch tổng số kẹo của hai người là nhỏ nhất có thể.

Input

• Dòng đầu tiên nhập số nguyên dương \(N\) – số gói kẹo \((2\le N\le{10}^4)\).
• Dòng thứ hai nhập \(N\) phần tử - số kẹo mỗi gói \((0 \le {a}_i\le{10}^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): Có \(N \le 20\).
• Subtask \(2\) (\(25\%\) số điểm): Có \(N \le 1000\), tổng số kẹo trong tất cả các gói không vượt quá \(3 \times {10}^4\).
• Subtask \(3\) (\(25\%\) số điểm): Có \(N \le 40\).
• Subtask \(4\) (\(25\%\) số điểm): Có \(N \le 10^4\), tổng số kẹo trong tất cả các gói không vượt quá \(12 \times {10}^5\).

Example

5
19 17 13 9 7

1