Đề bài

An và Bình là hai anh em. Ba của An 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 kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:

• Trước hết, ba của An chọn ra một số nguyên ~ k ~ (với ~ 1 \leq k \leq 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, ba của An 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.

Dữ liệu vào:

• Dòng đầu tiên gồm số nguyên ~ N ~ (~ 2 \leq N \leq 200000 ~) - số gói kẹo.
• Dòng thứ hai gồm ~ N ~ số nguyên ~ A_1, A_2, \dots, A_N ~ (~ 1 \leq A_i \leq 10^9 ~) - số viên kẹo trong từng gói kẹo.

Dữ liệu ra:

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

Ví dụ:

Dữ liệu vào:

5  
5 1 3 2 6  

Dữ liệu ra:

1  

Giải thích:

• Khi chọn ~ k = 3 ~:
  
  • An nhận các gói kẹo ~[5, 1, 3]~, tổng = ~ 9 ~.
  • Bình nhận các gói kẹo ~[2, 6]~, tổng = ~ 8 ~.
  • Chênh lệch = ~ |9 - 8| = 1 ~.

Chênh lệch nhỏ nhất là ~ 1 ~.

Giới hạn:

• ~ 2 \leq N \leq 200000 ~.
• ~ 1 \leq A_i \leq 10^9 ~.