Cho một dãy $A$ gồm $N$ số nguyên dương $A1,A2,\dots ,AN.$ Hãy chia dãy $A$ thành hai đoạn, đoạn thứ nhất gồm các phần tử đầu của dãy $A$, đoạn thứ hai gồm các phần tử còn lại.

Yêu cầu: Tìm cách chia sao cho độ chênh lệch giữa tổng các phần tử của hai đoạn là nhỏ nhất có thể.

Dữ liệu vào: Từ tệp chiadoan.inp gồm:

• Dòng đầu tiên gồm số nguyên $N(2\le N\le {10}^6)$
• Dòng thứ hai gồm N số nguyên dương $A1,A2,..,AN(1\le Ai\le {10}^9$ với $1\le i\le N)$.

Kết quả: Ghi ra tệp một số nguyên duy nhất là độ chênh lệch nhỏ nhất có thể.

INPUT

5
5 1 3 2 6

OUTPUT

1