22550번 - 時空のスゴロク・ロード 다국어

문제

全時空統一ディメンション・スゴロク・トーナメント。500 兆人を超える参加者の中から、ただ1人 のスゴロク絶対王者を決定するその大会に、あなたは21世紀の地球代表として参加している。

今あなたが挑戦している課題は、自分自身をコマとした1次元スゴロク。端のスタートマスから出発 して、1から6までの目が一つずつ書かれた巨大な6面ダイスを振って出た目の数だけ進むことを繰 り返す、あなたもよく知っている形式のスゴロクだ。スタートマスとは反対の端にあるゴールマスに 止まるとゴールとなる。もちろん、ゴールするまでにサイコロを振った回数が少なければ少ないほど 良い成績となる。

マスの中には特殊な効果を持ったマス「○しろまるマス進む」と「○しろまるマス戻る」が存在し、そこに止まってし まうと、指定されたマス数だけ進む、もしくは戻らなければならない。マスの効果で動いた結果、ふ たたび効果のあるマスに止まった場合は、続けて指示どおりに移動する。

しかし、これは一筋縄では攻略できない時空スゴロクだ。恐るべきことに、たとえば「3マス進む」 の3マス先に「3マス戻る」が置かれていることもありうる。このようなマスに止まり、マスの効果 で無限ループに陥ってしまった場合は、永遠にマスを往復し続けなければならない。

だが幸いなことに、あなたの身体には、望んだ事象を全事象に変えることのできる異能『確率湾曲』 が宿っている。この能力を使えば、サイコロの出目を自由に操ることも可能。このアドバンテージを 活かして、無限ループに陥らないようにしながら進んでいくとき、ゴールするまでにサイコロを振る 回数の最小値はいくつになるだろうか。

입력

N
p1
p2
.
.
.
pN

入力の1行目には、整数 N(3 ≤ N ≤ 100,000)が書かれている。これは、スゴロクのマス数をあらわす。マスには1 番からN 番までの番号がふられている。スタートのマスが1 番で、それからスタートに近い順に2 番、3 番、……、N - 1 番と続き、ゴールのマスがN 番である。i 番のマスでサイコロを振ってj の目が出たら、i + j 番のマスへと移動する。ただし、もしもi + j がN を超えていたら、余った数だけ戻ったりはせず、ゴールしたとみなされる。

続くN 行には、整数 p_i(-100,000 ≤ p_i ≤ 100,000)が書かれている。1 + i 行目に書かれた整数 p_i は、i 番のマスに書かれている指示をあらわす。p_i > 0 ならば「p_i マス進む」、p_i < 0 ならば「-p_i マス戻る」であり、p_i = 0 ならばそのマスには何の効果もない。p₁ とp_N は必ず0 である。マスの効果で、スタートより前やゴールより後に移動しろと指示されることはない。

なお、与えられるスゴロクは、ゴールすることが可能であると仮定してよい。

출력

ゴールするまでにサイコロを振る回数の最小値を出力せよ。

제한

힌트