Hangzhou is a beautiful city, especially the West Lake. Recently, the water level of the West Lake got lower and lower because of the hot weather. The experts think that the West Lake is under good situation if the water level is in a certain range. To maintain the good condition of the West Lake, we get at most 2 chances to pour or draw water.

So the question is:

There are **N** periods, each period the predicted water level of the West Lake is **Ai**(**Ai** could be under 0). Now, you can pour water **C** unit at period **X**. (if **c<0** then it means drawing water.)Then the water level from **period X** to **period N** will be increase **C**(if **c<0** then it means the water level will reduce **|C|**). But you have **at most 2 chances**.(Do nothing is OK!)

The government wants you to figure out the best plan that could make the periods that the water level is between 1 and N as many as possible.

There are multiple test cases. For each test case:

The first line only contains one integer ` N`(1<=

The second line contains

Process to the end of input.

One line for each test case. The maximal number of periods that could make the water level in good condition.

提交代码