Cho một dãy \(A\) gồm \(N\) số nguyên dương \(A1, A2,…,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ừ bàn phím gồm:

• Dòng đầu tiên gồm số nguyên \(N (2 ≤ N ≤ 10^6)\)
• Dòng thứ hai gồm N số nguyên dương \(A1, A2, .., AN (1 ≤ Ai ≤ 10^9 \) với \( 1 ≤ i ≤ 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