A1455.[COCI-2011_2012-contest4]#6 ZIMA

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.

The first line of input contains the integer N (1 ≤ N ≤ 100 000), 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 10
0.

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.

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

First sample description: 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.