問題文

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

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

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

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

制約

• $2 \leq N \leq 2 \times 10^5$　
• $1 \leq P_i \leq 10^9$ $(1 \leq i \leq N - 1)$
• 入力は全て整数

入力

出力

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

サンプル

4
1 2 3

2

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

4
1 1 1

3

5
4 3 2 1

1