You are the captain of a spaceship traveling through a series of n cosmic sectors. Your ship has an energy battery that starts at 0 units. As you travel through the sectors linearly, you encounter different cosmic phenomena represented by an array sectors.

• Positive values represent Energy Nebulas that charge your battery.
• Negative values represent Ion Storms that drain your battery.

You must decide whether to enter a sector or warp past it (skip it). Your ship's battery must never drop below zero, or you will be stranded in space. You must travel through the sectors in order from the first to the last.

Your task is to find and print the maximum number of sectors you can successfully visit.

Input

The first line contains one positive integer n 1 ≤ n ≤ 10^5

The second line contains n integers: s0, s1, ..., s(n-1) where: -10^9 ≤ si ≤ 10^9

Output

Print one integer, the maximum number of sectors the spaceship can safely visit.

Example

Input

6
10 -8 -7 -4 10 -2

Output

4