Boyan is the founder of a very cool startup. If there is one thing that startups need, it's money from angel investors. Investors are people that give money to startups, so that they can develop their idea, and later present it to the market.

When it comes down to giving money to startups, investors are very picky. Before investing in a startup, they will be asking all kinds of questions: the current financial situation of the startup, the idea, the number of software engineers working at the company, etc. Boyan is confident that he has a good idea, but the history of his startup is not that great. In some years, his company has had a profit (nonnegative balance at the end of the year), and in some years a loss (negative balance). For example, in the last five years, a company could have had the following results at the end of each year:

       -150   100   300   -400   200

In the first year, the company had a loss, in the second year a profit, etc. If we sum all the numbers, we see that in the last five years, this company actually did well, and had a total profit of 50: -150 + 100 + 300 - 400 + 200 = 50.

Given that investors are very picky, when Boyan talks to them, he doesn't want to start with negative results. In addition to that, he wants the sum of the numbers he presents to stay nonnegative during the entire presentation (so, the first number he presents should be nonnegative, the sum of the first two numbers should be nonnegative, the sum of the first three numbers should be nonnegative, etc). In order to do that, he decided to make just a small change in the order in which he presents the results for each year: instead of displaying the results for the first few years of his startup at the beginning, he will display those numbers at the end of his presentation. In other words, he will take some of the numbers from the start of the list (the results for the first years), and he will append them to the back of the list without changing their order. Let's call this operation a rotation. Here are the possible rotations of the numbers presented above:

       -150   100   300   -400   200
       100   300   -400   200   -150
       300   -400   200   -150   100
       -400   200   -150   100   300
       200   -150   100   300   -400

Looking at the second rotation, we can see that during the entire presentation of the numbers, the sum will stay nonnegative: 100 >= 0, 100 + 300 >= 0, 100 + 300 - 400 >= 0, 100 + 300 - 400 + 200 >= 0, and 100 + 300 - 400 + 200 - 150 >= 0. This is also true for the fifth rotation.

Before making any presentation plans for investors, Boyan wants to know for how many rotations of his company numbers, the sum will be nonnegative during the entire presentation?

Input

The first line of input contains one integer N (1 <= N <= 200 000), the number of years for which Boyan's company has results. In the second line, there are N integers Ai (-50 000 <= Ai <= 50 000), the results for each of those years (starting with the first one).

Output

The output consists of a single integer: the number of rotations for which the sum will be nonnegative (positive or 0) during the entire presentation.

Constraints

Time limit: 2 seconds
Memory limit: 256 megabytes

Examples

input
5
-150 100 300 -400 200

output
2

input
4
10 5 -5 0

output
3

Scoring

In test cases worth at least 20% of all points, 1 <= N <= 1 000.