JOI logo
第17回日本情報オリンピック 予選2

2017年12月11日
情報オリンピック日本委員会

問題
  双六 (Sugoroku) (配点 100点)

問題文

JOI 君はおじさんの家で双六を見つけた.双六は直線状に並んだ N+2 個のマスからなり,1 番目のマスはスタート,N+2 番目のマスはゴールである.その他の各マスには 0 または 1 が書かれていて,各 i (1≦i≦N) について,i+1 番目のマスに書かれた数字は A_i である.

双六では,最初にスタートのマスにコマを置き,サイコロを振って,出た目の数だけコマを進めることを繰り返す.ただし,1 の書かれたマスに止まった場合は,ゲームオーバーである.ゲームオーバーにならずにゴールのマスに止まるか,ゴールのマスを通り過ぎたら,ゲームクリアである.

JOI 君は双六を遊ぶためのサイコロをおもちゃ屋さんに買いに行くことにした.おもちゃ屋さんには N+1 個のサイコロが売っている.j 番目 (1≦j≦N+1) のサイコロは j 個の面を持ち,1,2,...,j1 つずつ書かれている.

JOI 君はゲームクリアできるようなサイコロのうち,最も面の数が少ないサイコロを 1 個買うことにした.JOI 君はどのサイコロを買えばよいだろうか.

制約

入力・出力

入力
入力は以下の形式で標準入力から与えられる.
N
A_1 A_2 ... A_N

出力
JOI 君が購入すべきサイコロの面の数を答えよ.

入出力例

入力例 1
5
0 1 0 0 0

出力例 1
2

双六は 7 マスからなり,3 マス目のみに 1 が書かれている.面の数が 2 個のサイコロを使った場合,例えば出た目が 1,2,1,1,1 となったときにゲームクリアすることができる.これが最小なので 2 を出力する.


入力例 2
5
1 1 1 1 1

出力例 2
6

双六は 7 マスからなり,スタートとゴール以外のマス全てに 1 が書かれている.このとき,面の数が 6 個のサイコロが必要である.これが最小なので 6 を出力する.


入力例 3
7
0 0 1 0 1 1 0

出力例 3
3