Migrated from Lutece 1483 吸血鬼家族

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你是一个专门研究吸血鬼家族树的系谱专家，吸血鬼家族树不同于人类家族树。特别的是，吸血鬼的出生方式与人类不同，创造一个全新吸血鬼的唯一方式是一个现存的老吸血鬼将一个人类转化为一只新的吸血鬼。每当发生这种情况，我们即认为老吸血鬼为主人，而新创造的吸血鬼是老吸血鬼的仆人。

在家族树上，我们定义两只吸血鬼之间的距离为一只吸血鬼沿着树边走到另一只吸血鬼的步数，特别的，仆人到自己的主人步数为$1$，任意一只吸血鬼到达自己的距离是$0$。

现在你在研究一个特殊的吸血鬼家族，这个家族有$N$个吸血鬼成员，编号为$0\sim N - 1$。特殊的，这个家族中有一位吸血鬼始祖（没有主人）。你并不知道这些家族成员的关系，但是，对于每只吸血鬼，你知道一个值$Ai$，对于吸血鬼始祖，代表有$Ai$只仆人，对于其他吸血鬼，代表有$Ai - 1$只仆人。

你要思考出一颗满足所有$A_i$的家族树，如果不存在这样一颗家族树，输出$-1$，否则找到并返回在所有可能的家族树中的任意两只吸血鬼距离的最大值。

Input

第一行包括一个整数T，表示有多组数据。

接下来T行，每行包括一个测试数据：

每个测试数据的第一行，包括一个整数N，表示有N个吸血鬼，（$1<=N<=10000$）

接下去一行包括N个整数，代表$0\sim N - 1$的$A_i$值。($1<=Ai<=N$)

Output

输出包括一行，表示在所有可能的家族树中的任意两只吸血鬼距离的最大值。如果不存在这样一颗家族树，输出-1。

Samples

1
20
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

-1

1
5
1 1 1 1 4

2

Resources

每周一题 div2