Nam rất thích làm toán đặc biệt các bài toán số học đặc biệt là các con số. Cho dãy số nguyên gồm ~n~ phần tử được đánh số từ ~1~ đến ~n~. Nam sẽ thực hiện thao tác sau một số lần (có thể ~0~ lần), mỗi thao tác Nam chọn ra hai phần tử ~a_i,a_{i+1}~ và một số nguyên bất kỳ ~k~ sau đó thực hiện ~a_i+k~ và ~a_{i-1}-k~. Nam cần thực hiện ít nhất bao nhiêu thao tác để dãy ~a~ thành dãy số không âm.

Cho dãy số ~a_1,a_2,\dots,a_n~ xác định số thao tác ít nhất để biến đổi dãy ~a~ thành dãy số chỉ chứa các số nguyên không âm.

Input

• Dòng ~1~ ghi số nguyên dương ~n~ ~(1 \le n \le 10^5)~.

• Dòng tiếp theo ghi dãy số nguyên ~a_1,a_2,\dots,a_n~ ~(-10^9 \le a_i \le 10^9)~.

Output

Ghi ra số thao tác biến đổi ít nhất, nếu không thực hiện lần biến đổi nào thì in ra ~-1~.

Scoring

Sample Input 1

5
-3 0 3 0 0

Sample Output 1

2

Sample Input 2

5
-8 0 15 3 -2

Sample Output 2

3

Notes

Ví dụ thứ ~2~:

• Thêm ~8~ cho ~a_1~ và trừ ~-8~ cho ~a_2~ dãy sẽ thành ~0,-8,15,3,-2~;

• Thêm ~8~ cho ~a_2~ và trừ ~-8~ cho ~a_3~ dãy sẽ thành ~0,0,7,3,-2~;

• Thêm ~-2~ cho ~a_4~ và cộng ~2~ cho ~a_5~ dãy sẽ thành ~0,0,7,1,0~.