Kẹo nhỏ

An và Bình là hai anh em.

Ba của An sau một chuyến đi công tác xa trở về, mua cho hai anh em \(N\) gói kẹo. Gói thứ \(i\) có \(A_i\) viên kẹo.

Để tránh việc tranh giành lẫn nhau, ba của An đưa ra cách chia như sau:

• Chọn một số nguyên \(k\) (\(1 \le k < N\)).
• An nhận các gói từ \(1\) đến \(k\), Bình nhận các gói từ \(k+1\) đến \(N\).

Để hai anh em vui vẻ, ba muốn chọn \(k\) sao cho chênh lệch tổng số viên kẹo giữa hai người là nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(N\) (\(2 \le N \le 200\,000\)) — số lượng gói kẹo.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(1 \le A_i \le 10^9\)) — số viên kẹo trong từng gói.

Output

In ra một số nguyên — chênh lệch nhỏ nhất có thể giữa tổng số viên kẹo của An và Bình.

Scoring

• Subtask 1 (\(50\%\)): \(N \le 2000\).
• Subtask 2 (\(50\%\)): Không có ràng buộc thêm.

Sample Input 1

5
5 1 3 2 6

Sample Output 1

1

Sample Input 2

6
4 5 3 6 1 2

Sample Output 2

3

Sample Input 3

2
100 100

Sample Output 3

0