Nhân dịp đi công tác về, Mẹ của An và Bình có mua \(N\) gói kẹo. Gói kẹo thứ \(i\) có \(a_i\) viên kẹo. Để chia kẹo đều cho hai anh em, Mẹ có cách chia như sau:

• Trước hết, Mẹ 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(1 ≤ k ≤ N)\), phần còn lại, các gói kẹo từ \(k+1\) đến \(N\) sẽ được chia cho Bình.

Yêu cầu: Hãy giúp mẹ chia kẹo sao cho lượng kẹo chênh lệch giữa hai người là nhỏ nhất có thể.

Input:

• Dòng đầu chứa hai số nguyên \(N (1 ≤ N ≤ 2*10^5)\) - Số gói kẹo.

• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,…,a_N (1 ≤ a_i≤ 10^9)\) – là số lượng các viên kẹo trong mỗi gói \(1 ≤ i ≤N\))

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi một số nguyên \(p\) là chênh lệch lượng kẹo nhỏ nhất có thể.

Sample Input

5   
5 1 3 2 6

Sample Output

1