Warning Days Maximization

Given the temperatures over \(N\) days, a day is called a frozen day if its temperature is less than \(0\). A maximal contiguous segment of frozen days is called an ice period with duration \(T\). For each finished ice period (i.e. not one that is ongoing), warning days are marked in the days immediately preceding its start according to the following rules:

• If an ice period has duration \(T\) and is not the longest among all ice periods, then the \(2T\) days immediately before its start are marked as warning days.
• If an ice period is the longest one (i.e. it has maximum \(T\)), then the \(3T\) days immediately before its start are marked as warning days. In case there are multiple longest ice periods, you may select exactly one to receive the bonus marking of \(3T\) days while all the others receive \(2T\) days.
• If an ice period is currently ongoing (i.e. it extends to the present day), then no warning days are marked for that ice period.

The warning intervals are taken only among the given \(N\) days (days outside the range \([1, N]\) are ignored), and if two intervals overlap, the overlapping days are counted only once.

Your task is to choose the bonus for one of the longest ice periods in order to maximize the total number of days that are in a warning state. Output this maximum number of warning days.

inputFormat

The first line contains an integer \(N\) (\(1 \le N \le 10^5\)) which is the number of days. The second line contains \(N\) space-separated integers where the \(i\)-th integer represents the temperature on day \(i\) (\(-10^9 \le temperature \le 10^9\)).

outputFormat

Output a single integer representing the maximum number of warning days.

sample

10
1 -1 -2 -3 4 -1 -2 1 -1 -2

8