题目内容

巡游筹备组在一条长街上依次挂了若干道彩门，计划用一辆花车把它们全部揭开。花车本身停在最左端不能挪位置，彩门由街面下的牵引索带动，从花车正前方经过。揭开第 $i$ 道彩门时，车上已有的绶带条数必须至少为 $w_i$；一旦揭开，这道门上的绶带会被收走，车上立刻多 1 条绶带。牵引索一开始把彩门从左往右送过花车，司机可以在任意时刻让牵引索换向，好让刚才因绶带不够而错过的彩门再经过一次。

初始时车上没有绶带，因此只能先揭 $w_i=`0`$ 的彩门。请对每一条任务求出：要揭开该街上全部彩门，至少需要换向多少次。若无论怎样换向都不可能揭完，则该任务的答案为 -1。

约束：

• 1 $\le$ $q$ $\le$ $10$
• 1 $\le$ $m$ $\le$ $5 \times 10^2$
• $w_i$ 为非负整数

输入描述

第一行一个整数 $q$（1 $\le$ $q$ $\le$ $10$），表示任务条数。

随后是 $q$ 个任务，每个任务两行：

• 第一行一个整数 $m$（1 $\le$ $m$ $\le$ $5 \times 10^2$），表示该街彩门数量
• 第二行 $m$ 个非负整数 $w_0,w_1,\ldots,w_{m-1}$，表示从左到右各道彩门所需的绶带条数

输出描述

输出 $q$ 行，每行一个整数：对应任务至少要换向的次数；若不可能揭完，输出 -1。

样例1

输入

3
3
0 1 2
2
1 0
1
4

输出

0
1
-1

说明

• 第一条：从左往右依次揭开 0、1、2，绶带刚好够用，不必换向。
• 第二条：先错过左边需要 1 条的门，揭开右边 $w=`0`$ 的门后车上有 1 条绶带，换向一次再揭左边那道。
• 第三条：只有一道门且需要 4 条绶带，初始为 0，无法揭开。

样例2

输入

1
3
1 0 2

输出

2

说明

• 第一趟从左到右：跳过需要 1 的门，揭开中间 $w=`0`$ 的门，此时绶带为 1，右边需要 2 条仍不够。
• 换向后从右到左：揭开左边那道，绶带变为 2。
• 再换向揭开右边那道。共换向 2 次。

样例3

输入

1
4
0 3 1 2

输出

1

说明

第一趟揭开第 1、第 3、第 4 道（需要 0、1、2），绶带变为 3；换向一次即可揭开剩下那道需要 3 条的门。