Give Back My Streak!

Interview

Time limit1sMemory limit1024 MB

Summary

Given daily problem counts, find the longest streak when a Streak Freeze covers zero-solve days and is rebought two days after each use.

Level: Medium5 of 10
Topics: Simulation, Greedy, Queue
Solved: No attempts yet

Statement

solved.ac is a community project that tags problems and assigns them difficulty levels. Users can also decorate their profiles with badges and backgrounds, and solved.ac hosts arenas.

solved.ac has a feature called the streak. A streak counts how many days in a row a user solved at least one problem. If you solved at least one problem every day for $x$ days, your streak is $x$ days. Solving two or more problems in a day counts the same as solving one. A longer streak unlocks badges, backgrounds, and other profile decorations.

Yehwan had been working hard on his streak on solved.ac to earn the Hanbyeol background. Then one day he fell asleep and did not solve any problems! His streak of 117 days broke. Now Yehwan plans to keep buying and equipping the 'Streak Freeze' item so that his streak never breaks again.

[Streak Freeze]

While a 'Streak Freeze' is equipped, it is used automatically on any day when no problem is solved. The streak does not increase on that day, but it does not break either. If a 'Streak Freeze' is equipped and the number of problems solved on day $i$ , $P_i$ , is 0, then we say the 'Streak Freeze' was used on day $i$ . To prevent abuse, at most one can be equipped at a time.

Yehwan does not check whether a 'Streak Freeze' is equipped. So when one is used on day $i$ , he buys and equips a new one on day $i+2$ . For example, if he solves no problems on day 1 and the freeze is used, he buys and equips a new one on day 3. He equips the freeze before he starts solving problems, so a freeze bought on a given day can be used that same day.

At the start, Yehwan begins solving problems with a 'Streak Freeze' already equipped. Given $N$ , the number of days he logged in to solve problems, and the number of problems he solved on each of those days, find the longest streak he can achieve.

Input

The first line contains $N$ , the number of days Yehwan logged in to solve problems.

The second line contains $P_1, P_2, \cdots, P_N$ , separated by spaces. $P_i$ is the number of problems solved on day $i$ .

Output

Print the longest streak Yehwan can achieve during this period.

Constraints

$1 \le N \le 1000$

$0 \le P_i \le 100$ for $1 \le i \le N$

Examples2

Example 1
Input
```
2
1 1
```
Expected output
```
2
```
Example 2
Input
```
3
1 0 2
```
Expected output
```
2
```