Có n gói kẹo. Gói thứ i có A[i] viên kẹo.

Không bóc các gói kẹo, hãy tìm cách chia hết các gói kẹo thành 2 phần sao cho tổng số viên kẹo của các phần gần bằng nhau nhất, hay nói cách khác, độ chênh lệnh của tổng viên kẹo của 2 phần là nhỏ nhất.

Input

• Dòng 1: Số n
• Dòng 2: n số nguyên dương A1, A2,..., An

Output

Độ chênh lệch nhỏ nhất của số viên kẹo của 2 phần.

Ví dụ

Input

5
4 7 9 3 3

Output

0

Input

4
3 10 3 2

Output

2

Ràng buộc:

• Subtask 1: n ≤ 100; Ai ≤ 1000;
• Subtask 2: n ≤ 1000; Ai ≤ 100;