Tinh thể

Bạn là một phi hành gia đang thực hiện nhiệm vụ khám phá một hành tinh xa xôi. Con tàu của bạn đã hạ cánh xuống bề mặt hành tinh, và bạn cần thu thập các tinh thể năng lượng để duy trì hệ thống sự sống của mình.

Trên hành tinh này có \(n\) điểm thu thập tinh thể được đánh số từ \(1\) đến \(n\). Mỗi điểm thu thập chứa một tinh thể có giá trị năng lượng \(a_i\). Nếu \(a_i\) là số dương, bạn nhận thêm năng lượng. Nếu \(a_i\) là số âm, bạn sẽ bị tiêu hao năng lượng nếu thu thập tinh thể này.

Bạn có thể chọn thu thập hoặc bỏ qua từng tinh thể theo thứ tự từ trái sang phải, nhưng tổng năng lượng bạn đang có không bao giờ được phép âm.

Yêu cầu. Hãy xác định số lượng tinh thể nhiều nhất có thể thu thập được.

Input

Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — số điểm thu thập tinh thể.

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\)) — giá trị năng lượng của các tinh thể.

Output

In ra một số nguyên duy nhất — số lượng tinh thể lớn nhất có thể thu thập được.

Input

%
6
4 -4 1 -3 1 -3

Output

%
5

Notes

Trong ví dụ trên, có thể thu thập \(5\) tinh thể ở các vị trí \(1, 2, 3, 4, 5\).

Scoring

• (50%) \(1 \le n \le 2000\).
• (50%) Không có ràng buộc bổ sung.