Sequence Move 2

2 secs 1024 MB
AiletS

問題文


一列で並んだ 個のマスがあります。左から 番目のマスを「マス 」 とします。マス には整数 が書かれています。

今 AiletS くんはマス1にいます。AiletS くんは以下の操作を繰り返し、マス に行くことが目標です。

  • AiletS くんが マス にいる時、1 以上 以下の整数 を選ぶ。現在のマス からマス に移動する

マス にちょうど到着するための操作回数の最小値を求めてください。もし、到達できない場合は -1 を出力てください。

制約


  •  
  • 入力は全て整数

入力


...

出力


操作回数の最小値を出力してください。

サンプル


入力1
4
1 2 3
出力1
2

頂点1 頂点2 頂点4 のように移動するのが最適です。2回より小さい操作回数で頂点4に到達することはできないため、2を出力します。

入力2
4
1 1 1
出力2
3
入力3
5
4 3 2 1
出力3
1

提出


Go (1.14)