题目背景

戈壁上架起了一排信标，用来把消息一站一站接力传下去。每座信标能覆盖的范围写在它的铭牌上，可每座信标都要耗电，能少转发几次就少转发几次。调度员想先算清：从最西边的信标发出的一条消息，最少要经过几次转发才能抵达最东边的信标。

题目描述

信标共有 $n$ 座，从西到东编号 $1 \sim n$。第 $i$ 座信标的铭牌上写着整数 $r_i$，表示它可以把消息直接发给编号在 $i \sim \min(n, i + r_i)$ 范围内的任意一座信标（包括它自己）；超出序列范围的部分没有信标。

消息最初由 $1$ 号信标发出。每完成一次转发，消息就从当前持有它的信标交到另一座信标手上，转发次数增加 $1$。请求出消息抵达 $n$ 号信标所需的最少转发次数；如果怎么转发都到不了 $n$ 号信标，输出 -1。

特别地，当 $n = 1$ 时消息已经在目标信标上，转发次数为 $0$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $r_1, r_2, \dots, r_n$。

输出格式

一行一个整数，表示最少转发次数，或 -1。

输入输出样例 #1

输入 #1

5
2 1 1 1 0

输出 #1

3

输入输出样例 #2

输入 #2

3
1 0 0

输出 #2

-1

输入输出样例 #3

输入 #3

1
0

输出 #3

0

说明

样例解释

样例 1 中 $1$ 号信标射程为 $2$，可以直接发给 $2$ 号或 $3$ 号信标。先发给 $3$ 号信标（第 $1$ 次转发），$3$ 号再发给 $4$ 号（第 $2$ 次），$4$ 号发给 $5$ 号（第 $3$ 次），共 $3$ 次。若先发给 $2$ 号信标，$2$ 号射程只有 $1$，最远到 $3$ 号，之后的走法相同，次数不会更少。

样例 2 中 $1$ 号信标只能把消息发给 $2$ 号信标，而 $2$ 号信标射程为 $0$，只能发给自己，消息永远到不了 $3$ 号信标。

样例 3 中只有一座信标，消息已经在目标位置上，转发次数为 $0$。

数据范围

• 对于 $30\%$ 的数据，$n \le 300$；
• 对于 $60\%$ 的数据，$n \le 5000$；
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le r_i \le 10^9$。