Sangbeom's Melancholy

Minkyun has predicted Sangbeom's mood for the next N days.

Each day's mood is represented by an integer. A day with a negative mood is depressed, and a maximal consecutive interval of negative mood values is called a depressed period.

For a depressed period of length T, Minkyun must give flowers from 2T days before the period starts through the day immediately before it starts. For exactly one of the longest depressed periods, the interval starts 3T days before the period starts instead of 2T days before it. If there are several longest depressed periods, only one of them may use the 3T rule; the others use the 2T rule.

Only days among the predicted N days are counted. If a required flower interval begins before the first predicted day, count as many days as are available starting from day 1.

Choose the longest period that uses the 3T rule so that the number of distinct days on which Minkyun gives flowers is maximized. Find that maximum number of days.

The first line contains the number of predicted days N (1 <= N <= 100,000).

The second line contains N integers representing Sangbeom's mood on each day. The absolute value of each mood is at most 100.

Output the maximum number of days on which Minkyun must give flowers.