题目描述

一只青蛙要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子，每隔一米就有一个，每个桩子上都有一个弹簧，青蛙跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为 \(5\)，就代表青蛙下一跳最多能够跳 \(5\) 米，如果为 \(0\)，就会陷进去无法继续跳跃。河流一共 \(N\) 米宽，青蛙初始位置就在第一个弹簧上面，要跳到最后一个弹簧之后就算过河了，给定每个弹簧的力量，求青蛙最少需要多少跳能够到达对岸。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤30000)\)，表示河流宽度（即桩子个数），第二行为 \(n\) 个非负整数 \(a_i(≤30)\)，表示每个桩子上弹簧的力量值。

输出格式

对于每组数据，输出最少跳跃数，如果无法到达，则输出 \(-1\)。

样例1

输入样例1

2
5
2 0 1 1 1
5
2 0 3 1 1

输出样例1

4
2

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("river.in","r",stdin);
freopen("river.out","w",stdout);