Description

You are given the temperatures over $N$ days. Define:

• If the temperature of a day is less than $0$, then it is called a freezing day.
• If there are $T$ consecutive freezing days, then this is called a cold period of duration $T$.

Several days before a cold period starts will be marked as being in an alert state. For a cold period with duration $T$, the rules are:

• If this cold period is not the longest among all cold periods, then the $2T$ days before it starts are marked as alert days.
• If this cold period is the longest among all cold periods, then the $3T$ days before it starts are marked as alert days. In particular, if there are multiple longest cold periods, only one of them is marked for $3T$ days, and the others are marked for $2T$ days.
• If you are currently inside a cold period, you are not allowed to mark alert days for the current cold period, but if the conditions allow, you may mark alert days for future cold periods.

You may choose any one of the longest cold periods so that the $3T$ rule is applied to it. Among all choices, find the maximum possible number of alert days.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ integers $T_i$, representing the temperatures over these $N$ days.

Output Format

Output the maximum number of days that are in the alert state.

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

6

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

8

Hint

[Sample 1 Explanation]

There are $3$ longest cold periods: $\texttt{-1; -2; -3}$.

When choosing $\texttt{-2}$ as the cold period that needs $3T$ days marked as alert before it starts, the number of alert days is maximized:

[Constraints]

• For $40\%$ of the testdata, the longest cold period is unique.
• For $100\%$ of the testdata, $1 \le N \le 10^5$, $|T_i| \le 100$.

[Hints and Notes]

Translated from COCI 2011-2012 CONTEST #4 Task 2 ZIMA.

The score of this problem follows the original COCI setting, with a full score of $100$. Since Luogu does not support non-integer scores, adjustments were made for cases where the score cannot be divided evenly.

Translated by ChatGPT 5