JOI 군은 삼촌 집에서 주사위 쌍육을 발견했다. 판은 일렬로 늘어선 \(N+2\)칸으로 되어 있고, \(1\)번 칸은 출발, \(N+2\)번 칸은 도착이다. 나머지 칸에는 \(0\) 또는 \(1\)이 적혀 있다. 각 \(i\) (\(1 \le i \le N\))에 대해 \(i+1\)번 칸에 적힌 숫자는 \(A_i\)이다. 처음에는 출발 칸에 말을 놓고, 주사위를 굴려 나온 눈만큼 말을 앞으로 옮기기를 반복한다. \(1\)이 적힌 칸에 멈추면 게임 오버이다. 게임 오버가 되지 않고 도착 칸에 멈추거나 도착 칸을 지나치면 게임 클리어이다. JOI 군은 장난감 가게에서 주사위를 사려 한다. 가게에는 \(N+1\)개의 주사위가 있다. \(j\)번째 (\(1 \le j \le N+1\)) 주사위는 면이 \(j\)개이고, \(1, 2, \ldots, j\)가 하나씩 적혀 있다. JOI 군은 게임 클리어가 가능한 주사위 가운데 면의 수가 가장 적은 것을 하나 사려고 한다. 사야 할 주사위의 면의 수를 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
- 첫째 줄에 정수 \(N\)이 주어진다.
- 둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \ldots, A_N\)이 공백 하나로 구분되어 주어진다.
- \(1 \le N \le 100\)
- \(0 \le A_i \le 1\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 JOI 군이 사야 할 주사위의 면의 수를 출력한다.
판은 \(7\)칸이고 \(3\)번 칸에만 \(1\)이 있다. 면이 \(2\)개인 주사위를 쓰면, 예를 들어 눈이 \(1, 2, 1, 1, 1\)로 나와 클리어할 수 있다. 이보다 면이 적은 주사위로는 클리어할 수 없으므로 \(2\)를 출력한다.
출발과 도착을 뺀 칸에 모두 \(1\)이 있다. 면이 \(6\)개인 주사위가 필요하고, 이것이 최소이므로 \(6\)을 출력한다.