#606. CANDY - Chia kẹo

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề 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 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 ≤ 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, 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 ≤ N ≤ 200000) - 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.

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
Dữ liệu vào:
6
4 5 3 6 1 2

Dữ liệu ra:

3
Dữ liệu vào:
2
100 100

Dữ liệu ra:

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 .
  • Trong ví dụ thứ hai, có hai cách chọn k tối ưu:
    • Chọn k = 2 . Tổng số kẹo An được chia là 4 + 5 = 9 , tổng số kẹo Bình được chia là 3 + 6 + 1 + 2 = 12 , chênh lệch lượng kẹo là |9 − 12| = 3 .
    • Chọn k = 3 . Tổng số kẹo An được chia là 4 + 5 + 3 = 12 , tổng số kẹo Bình được chia là 6 + 1 + 2 = 9 , chênh lệch lượng kẹo là |12 − 9| = 3 .

Giới hạn:

  • Subtask \#1 (50\%\text{ số điểm}): N ≤ 2000 ;
  • Subtask \#2 (50\%\text{ số điểm}): Không có ràng buộc gì thêm.