Cho mảng \(A\) gồm \(n\) số nguyên. Đếm số lượng mảng con có tổng không âm.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).

Output

• In ra số lượng mảng con.

Điều kiện

• \(1 \le n \le 10^6\).
• \(0 \le |A_i| \le 10^9\).

Ví dụ

Input:

3
1 -2 1

Output:

3