In the old times, when dragons ruled the land, air temperature never fell below zero degrees. But after dragons left, nice and warm times went with them.

We say that day is a winter day when average temperature for that day is below zero. We say that $T$ consecutive winter days form a winter period of length $T$.

There are some people that annoy everyone by rambling on about some winter that is coming. So a law had to be made, stating that you are allowed to say that winter is coming at most $2T$ days before a winter period of length $T$. Exception to this is only the winter period with the longest length, that can be announced at most $3T$ days before it begins. During some winter period, you can't say that this period is coming, since it's already here, but you can announce future winter periods according to the rules above. If there are more than one winter periods with the longest length, then only one is chosen and $3T$ days rule is applied only to that period.

Knowing expected temperatures for some time period, find out the maximum number of days during which it is allowed to say that winter is coming.

Input Specification

The first line of input contains the integer $N$ $(1\le N\le 100000)$, length of the overall time period we are considering. The following line contains $N$ integers, temperatures of consecutive days in considered period. Absolute values of these integers won't exceed $100$.

Output Specification

The first and only line of output should contain the maximum number of days during which it is allowed to announce the winter is coming.

Scoring

In test cases worth $40\mathrm{\%}$ of total points, there will be only one winter period with the longest length.

Sample Input 1

8
1 -1 4 3 8 -2 3 -3

Sample Output 1

6

Explanation for Sample Output 1

There are three winter periods of length one. In order to obtain the requested maximum, best thing to do is to choose the second one to apply the $3T$ days rule, and starting announcing it three days before it arrives.

Sample Input 2

15
1 2 -1 2 3 4 5 6 1 4 8 3 -1 -2 1

Sample Output 2

8