Davion là một hiệp sĩ. Anh được phép của nhà vua để được tiến quân đánh giặc. Davion sẽ đi qua \(N\) thành phố theo thứ tự từ 1 đến \(N\). Một số thành phố chưa bị giặc xâm chiếm nên sẽ giúp Davion bằng cách tuyển thêm chiến binh cho anh ấy, giúp cho quân số của anh ấy tăng lên. Còn nhưng thành phố đã bị địch chiếm sẽ luôn cản đường Davion, khiến cho quân số của anh ấy giảm xuống. Davion chỉ dừng cuộc tấn công khi quân số của anh ấy nhỏ hơn 0 hoặc anh ấy đi qua cả \(N\) thành phố. Hãy trả về kết quả cuộc tấn công của Davion.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

int solve(int N, int A[])

• \(N\): số thành phố.
• \(A[]\): mảng gồm \(N\) phần tử, nếu \(A_i\) (\(0 \le i < N\)) dương có nghĩa là thành phố thứ \(i+1\) chưa bị chiếm và Davion có thể chiêu mộ thêm \(A_i\) quân, ngược lại là thành phố \(i+1\) đã bị chiếm và Davion cần tốn \(|A_i|\) quân để vượt qua thành phố này.
• Hàm này cần trả về một số nguyên:
  • Nếu Davion đi qua tất cả \(N\) thành phố, hàm này cần trả về số nguyên có giá trị bằng \(-1\).
  • Nếu Davion dừng chân ở thành phố thứ \(i\) (\(0 \le i < N\)), hàm này cần trả về số nguyên có gía trị bằng \(i+1\).
• Hàm này được gọi đúng một lần.

Constraint

• \(1 \le N \le 10^5\).
• \(|A_i| \le 1000\).

Ví dụ

Xét lời gọi hàm sau:

solve(4,[5,2,-4,6])

Trong ví dụ này, \(N = 4, A = [5,2,-4,6]\).

Khi khởi đầu, Davion có \(0\) quân.

Khi đi qua thành phố \(0\), Davion có thể chiêu mộ thêm \(5\) quân. Số quân của Davion lúc này là \(5\).

Khi đi qua thành phố \(1\), Davion không cần chiêu mộ thêm quân. Số quân của Davion lúc này là \(5\).

Khi đi qua thành phố \(2\), Davion phải đánh nhau và mất \(4\) quân. Số quân của Davion lúc này là \(1\).

Khi đi qua thành phố \(3\), Davion không cần chiêu mộ thêm quân. Đây là thành phố cuối cùng. Davion có thể vượt qua cả \(N\) thành phố.

Vậy hàm cần trả về một số nguyên có giá trị bằng \(-1\).