Cho một dãy gồm ~n~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~. Tìm đoạn con liên tiếp dài nhất có tổng không âm.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~ (~|a_i| \leq 10^9)~.

Output

In ra độ dài đoạn con thoả mãn. Nếu không tồn tại đoạn con thoả mãn in ra -1.

Subtasks

• Subtask ~1~ (~50\%~): ~n \leq 10^3~.
• Subtask ~2~ (~50\%~): Không có điều kiện gì thêm.

Sample Test

Input:

5
-1 -1 2 -2 -3

Output:

3