{"code":"candydiv","name":"Chia kẹo","description":"An và Bình là hai anh em. Ba của An sau một 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:\r\n- Trước hết, ba của An chọn ra một số nguyên $k$ (với $1 \\leq k \\leq N$)\r\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.\r\n\r\nĐể 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.\r\n\r\n

Input

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

Output

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

Scoring

\r\n\r\n - Subtask $1$ ($50\\%$ số điểm): $N \\le 2000$.\r\n - Subtask $2$ ($50\\%$ số điểm): không có ràng buộc gì thêm.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5\r\n 5 1 3 2 6\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 1\r\n ```\r\n \r\n ??? warning \"Note\"\r\n 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$.\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 6\r\n 4 5 3 6 1 2\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 3\r\n ```\r\n \r\n ??? warning \"Note\"\r\n Trong ví dụ thứ hai, có hai cách chọn k tối ưu:\r\n – 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$.\r\n – 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$.\r\n\r\n!!! question \"Test 3\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 2\r\n 100 100\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 0\r\n ```\r\n \r\n*Nguồn: Free Contest*","points":900.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}