주사위 놀이 (Sugoroku)

면접 대비

시간 제한2초메모리 제한512 MB

요약

2번부터 N+1번 칸에 0 또는 1이 적혀 있을 때, 1부터 j까지의 눈금을 굴려 1이 적힌 칸에 멈추지 않고 N+2번 칸에 도달하거나 지나칠 수 있는 가장 작은 주사위 면 수 j를 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, BFS, 그래프, 그리디
정답자: 아직 제출이 없습니다

문제

JOI 군은 삼촌 집에서 주사위 놀이판을 발견했다. 놀이판은 일직선으로 놓인 $N+2$ 개의 칸으로 이루어져 있고, 1번 칸이 출발점, $N+2$ 번 칸이 도착점이다. 나머지 칸에는 0 또는 1이 적혀 있으며, 각 $i$ ( $1 \le i \le N$ )에 대해 $i+1$ 번 칸에 적힌 숫자는 $A_i$ 이다.

놀이는 말을 출발점에 놓고 시작한다. 그다음 주사위를 굴려 나온 눈의 수만큼 말을 앞으로 옮기는 동작을 반복한다. 1이 적힌 칸에 말이 멈추면 게임 오버다. 1이 적힌 칸에 한 번도 멈추지 않고 도착점에 정확히 멈추거나 도착점을 지나치면 게임 클리어다.

JOI 군은 놀이에 쓸 주사위를 사러 장난감 가게에 갔다. 가게에는 주사위 $N+1$ 개를 판다. $j$ 번째 ( $1 \le j \le N+1$ ) 주사위는 면이 $j$ 개이고, 각 면에 $1, 2, \dots, j$ 가 하나씩 적혀 있다.

주사위 눈이 어떤 순서로 나오면 게임을 클리어할 수 있는 주사위 중에서, JOI 군은 면의 수가 가장 적은 주사위 하나를 사기로 했다. JOI 군은 어떤 주사위를 사야 하는가?

입력

입력은 표준 입력으로 다음 형식으로 주어진다.

N
A_1 A_2 ... A_N

출력

JOI 군이 사야 할 주사위의 면의 수를 한 줄에 출력한다.

제한

$1 \le N \le 100$
$0 \le A_i \le 1$ ( $1 \le i \le N$ )

예제3

예제 1
입력
```
5
0 1 0 0 0
```
예상 출력
```
2
```
예제 2
입력
```
5
1 1 1 1 1
```
예상 출력
```
6
```
예제 3
입력
```
7
0 0 1 0 1 1 0
```
예상 출력
```
3
```