Sean is writing the marking guide for the prospective FIT1008 Hurdle test, and he has a good idea of how students will fare on each question (essentially, how many marks students will get on each question; his estimate may include negative numbers, as this version of the test has negative marking!).

Sean doesn't want to completely demotivate the students. Students will be demotivated if, at any point while completing the test from start to finish, the students are expected to currently have a negative test score. Sean has the ability to strike questions from the test, and the remaining questions are attempted in the same order. Sean likes the questions, though, and wants to strike as few questions as possible while keeping students motivated.

Can you help Sean decide which questions from the test to include?

In order to pass the tests, your solution should have a time complexity of ~O(n\ \log(n))~.

Input

Input will begin with a single integer ~n~ (~1 \leq n \leq 10^5~) - the total number of questions on the test.

The next line will contain ~n~ integers ~a_1, a_2, \ldots, a_n~ (~-10^9 \leq a_i \leq 10^9~) - the expected mark that the students will receive on the ~i^{\text{th}}~ question.

Output

Output a single integer - the maximum number of questions that Sean can keep in the test without students being demotivated.

Example 1

Input

6
4 -4 1 -3 2 -3

Output

5

If the test was left as is, then students would get demotivated after taking the 4th question. If we remove either of the first two questions that will receive negative marks, then the test doesn't have this issue.

Example 2

Input

4
1000 1000 1000 1000

Output

4

Hopefully this is how your actual Hurdle test goes :)