30395번 - 내 스트릭을 돌려내!

문제

백준 온라인 저지(BOJ)에는 문제들에 태그와 난이도를 붙이는 커뮤니티 프로젝트인 solved.ac가 있다. 이외에도 뱃지 또는 배경을 통해 프로필을 꾸밀 수 있고, 아레나를 개최하고 있다.

solved.ac에서는 스트릭이라는 요소가 존재하는데, 이는 백준에서 하루에 한 문제 이상을 며칠 동안 연속으로 풀었는지 보여주는 지표다. 총 $x$일 동안 매일 1문제 이상을 빠짐없이 풀었다면 스트릭 $x$일이라고 한다. 그러나, 하루에 한 문제 이상 풀더라도 스트릭 계산 시에는 1문제 해결과 동일하게 취급된다. 스트릭 기간이 길어지면 뱃지와 배경 등 다양한 프로필 꾸미기 요소를 지급 받을 수 있다.

예환이는 한별이 배경을 얻기 위해 solved.ac에서 열심히 스트릭을 이어 나가고 있었다. 그러던 어느 날, 깜빡하고 잠이 들어 문제를 풀지 못했다! 117일 동안 유지했던 스트릭이 끊어진 예환이는, '스트릭 프리즈'라는 아이템을 계속 구입한 뒤 장착해서 스트릭을 더 이상 끊기지 않도록 할 것이다.

[스트릭 프리즈]

'스트릭 프리즈'는 장착하면 하루에 문제를 한 문제도 풀지 않은 경우 자동으로 사용되며, 스트릭이 늘어나지는 않지만 끊기지 않게 해준다. '스트릭 프리즈'가 장착되어 있고, $i$일에 푼 문제 수 $P_i$가 0이라면, '스트릭 프리즈'가 $i$일에 사용되었다고 정의하자. 하지만, 남용을 막기 위해 최대 1개만 장착할 수 있다.

하지만 예환이는 '스트릭 프리즈'의 장착 여부를 잘 확인하지 않기 때문에 '스트릭 프리즈'가 $i$일에 사용될 경우, $i+2$일에 새로운 '스트릭 프리즈'를 구매 후 장착한다. 예를 들어, 1일에 문제를 해결하지 않아 '스트릭 프리즈'가 사용되었다면 3일에 새로운 '스트릭 프리즈'를 구입한 뒤 장착한다. 예환이는 '스트릭 프리즈'를 장착한 후 문제를 풀기 시작하므로, 그날 산 '스트릭 프리즈'가 당일 사용되는 것 역시 가능하다.

예환이는 처음에 '스트릭 프리즈'를 장착한 채로 문제를 풀기 시작한다. 예환이가 문제를 해결했던 기간 $N$과 $N$일 동안 푼 문제 수의 기록이 주어질 때, 예환이의 최장 스트릭을 구해 보자.

입력

첫 번째 줄에는 예환이가 문제를 풀기 위해 접속한 일 수 $N$이 주어진다.

두 번째 줄에는 예환이가 푼 문제 수 $P_1,ドル$P_2,ドル $\cdots,ドル $P_N$이 공백으로 구분되어 주어진다. $P_i$는 $i$일차에 푼 문제 수를 의미한다.

출력

해당 기간동안 예환이가 이룰 수 있는 최장 스트릭을 출력한다.

제한

• 1ドル \le N \le 1000$
• $ 0 \le P_i \le 100 (1 \le i \le N)$

힌트