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.

Dữ liệu vào:
    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ả ra: 
In ra chênh lệch lượng kẹo nhỏ nhất có thể.

INPUT
5
5 1 3 2 6
6
4 5 3 6 1 2
2
100 100

OUTPUT
1
3
0