On a planet lying on the brink of the Milky Way, called AFWP-700, there is a very rare type of gem. This gem has magical properties. This gem is very expensive but it affects the person carrying it. Depending on the potency of the collected gem, it may boost a person's stamina or reduce it. Mike, a researcher on planet AFWP-700 must navigate through the planet's tough terrain in a certain path from Base A to Base B. On the way, he must collect at most n gems in the given order and then reach Base B.
Mike must go through the path and if he encounters a gem, he must either pick it up or destroy it (to avoid being affected by it). Having researched the different potencies of the gem, a numerical value is known for the potency of the gems. Mike must keep his potency non-negative throughout the trip.
Output the maximum number of gems that Mike can collect.
Input Format for Custom Testing
The first line contains an integer n, the total gems along the path.
The next line contains n space separated integers (a_i for all 1 ≤ i ≤ n).
Output Format
A single integer containing the maximum number of gems that Mike can collect without having negative stamina at any point.
Example 1:
Input: gemPotencies = [1, 2, 3, 4, -15]
Output: 4
Explanation:Mike can collect the first four gems without any hesitations but he cannot collect the last in any possible scenario.
Example 2:
Input: gemPotencies = [1, -2, 3, -4, 0]
Output: 4
Explanation:Here, Mike will always collect the first gem, then he will skip and break the second gem, collecting the third gem, totaling a stamina of 4. Now, he can collect the last 2 gems while keeping his stamina 0, but still not negative.
1 ≤ n ≤ 10^5-10^9 ≤ a_i ≤ 10^9
input:
output: