Reference: Codeforces 1526C2 — Potions, Hard Version

There are ~n~ potions arranged from left to right. Drinking potion ~i~ changes your health by ~a_i~.

A positive value increases your health, while a negative value decreases it.

You begin with ~0~ health and visit the potions in their given order. At each potion, you may either drink it or ignore it. Your health must never become negative after drinking a potion.

Find the maximum number of potions you can drink.

Input

• The first line contains one integer ~n~.
• The second line contains ~n~ integers: ~a_1, a_2, \ldots, a_n~.

Output

• Print one integer: the maximum possible number of potions you can drink.

Constraints

• ~1 \le n \le 2 \times 10^5~
• ~-10^9 \le a_i \le 10^9~

Example 1

Input:

6
4 -4 1 -3 1 -3

Output:

5