An và Bình là hai anh em. Ba của họ sau chuyến đi công tác xa nhà trở về, mua cho An và Bình ~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, hai anh em đã thống nhất việc chia kẹo theo cách sau:

Trước hết, người cha sẽ chọn ra một số nguyên ~k~ (~1≤k≤n~).

An sẽ được chia các gói kẹo từ 1 đến ~k~. Phần còn lại (các gói kẹo từ ~k+1~ đến ~n~) sẽ được chia cho Bình.

Để tránh sự phân bua giữa hai anh em, người cha muốn lựa chọn chỉ số ~k~ sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.

Yêu cầu

In ra chênh lệch lượng kẹo nhỏ nhất có thể.

Dữ liệu

Cho từ tệp CANDY.INP

Dòng đầu tiên gồm số nguyên ~n~ (~2≤n≤2*10^5~) số gói kẹo.

Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ (~1≤a_i≤10^9~) số viên kẹo trong từng gói kẹo.

Kết quả

Ghi ra file "ARR_A1.OUT"

In ra chênh lệch lượng kẹo nhỏ nhất có thể.

Ví dụ

Input1

5

5 1 3 2 6

Output1

1

Input2

6

4 5 3 6 1 2

Output2

3

Input3

2

100 100

Output3

0

Giải thích:

Trong ví dụ thứ nhất, nếu chọn k=3 thì tổng số kẹo An được chia là ~5 + 1 + 3 = 9~, tổng số kẹo Bình được chia là ~2 + 6 = 8~, chênh lệch lượng kẹo là |9 ~-~ 8| = 1.

Giới hạn:

-50% số test đầu tiên N≤2000;

-50% số test cuối cùng không có ràng buộc gì thêm.