An và Bình là hai anh em. Ba của An sau chuyến công tác xa nhà, 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 chia kẹo theo cách sau:

• Ba An chọn một số nguyên \(k (1 ≤k≤n).\)

• An nhận các gói kẹo từ gới thứ \(1\) đến gói thứ \( k\). Phần còn lại (gói thứ \(k+1\) đến gói thứ \(n\)) sẽ chia cho Bình.

Yêu cầu: Tìm số nguyên \(k\) sao cho chênh lệch kẹo giữa An và Bình là nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n(2≤n≤2×10^5 );\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤10^9).\)

Output

• In ra chênh lệch nhỏ nhất có thể

Ràng buộc

• Subtask 1: 50% số điểm với \(n ≤2000).\)

• Subtask 1: 50% số điểm với \(n ≤2×10^5).\)

Sample Input

5
5 1 3 2 6

Sample Output

1