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 tỉnh, 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. Nếu a là số dương, bạn nhận thêm năng lượng. Nếu a 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ể, nhưng tổng năng lượng của bạn không bao giờ được phép âm. Mục tiêu của bạn là thu thập nhiều tinh thể nhất có thể khi di chuyển từ điểm đầu tiên đến điểm cuối cùng.

Dữ liệu: Vào từ thiết bị nhập chuẩn

Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 2x10^5) - số điểm thu thập tinh thể.

Dòng thứ hai chứa n số nguyên a (-10^9 ≤ a ≤ 10^9) - giá trị năng lượng của từng tinh thể.

Kết quả: Ghi ra thiết bị xuất chuẩn một số nguyên duy nhất - số lượng tinh thể tối đa.

Ví dụ

Input:

6
4 -4 1 -3 1 -3

Output:

5

Giải thích: Bạn có thể thu thập 5 tinh thể 1, 3, 4, 5, 6

50% số điểm ứng với các test có 1 ≤ n ≤ 2000.

50% số điểm còn lại không có ràng buộc bổ sung.