겨울

프로그램 명: coci_zima

제한시간: 1 초

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. 우리는 영하로 떨어질때의 날을 겨울 날이라고 한다. 연속한 T 날의 겨울날을 크기 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.

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 100.

출력

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.

입출력 예

input

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

output

6

input

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

output

8

SAMPLE TESTS

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.

Day 1. 2. 3. 4. 5. 6. 7. 8.

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

Winter no yes no no no yes no yes

Winter is coming yes no yes yes yes yes yes no

출처:coci 2012 contest5 2/6

[질/답] [제출 현황] [푼 후(1)]

[ 채 점 ] [홈으로] [뒤 로]

Day	1.	2.	3.	4.	5.	6.	7.	8.
Temperature	1	-1	4	3	8	-2	3	-3
Winter	no	yes	no	no	no	yes	no	yes
Winter is coming	yes	no	yes	yes	yes	yes	yes	no