Tổng âm

Hồng đang ghi lại mức thay đổi lợi nhuận theo từng ngày.
Mỗi ngày có một giá trị \(A_i\) (có thể âm, dương hoặc bằng \(0\)).
Hồng muốn chọn một giai đoạn liên tiếp sao cho tổng thay đổi trong giai đoạn đó là âm.

Một dãy con liên tiếp là đoạn \([l,r]\) với \(1 \le l \le r \le N\).

Yêu cầu. Hãy tìm độ dài lớn nhất của một dãy con liên tiếp có tổng âm.
Nếu không tồn tại dãy con nào có tổng âm, in ra \(0\).

Input

• Dòng đầu chứa số nguyên \(N\) \((1 \le N \le 200000)\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) \((-10^9 \le A_i \le 10^9)\).

Output

• In ra một số nguyên là độ dài lớn nhất của dãy con liên tiếp có tổng âm (hoặc \(0\) nếu không có).

Lưu ý: Có \(50\%\) số điểm ứng với \(N \le 2000\).

Input

%
5
2 -3 1 -2 4

Output

%
4

Notes

Ví dụ trên, đoạn \([1,4]\) có tổng \(2 + (-3) + 1 + (-2) = -2\) là âm và có độ dài \(4\) (là lớn nhất).