n 个整数排成一圈,定义一次操作为:选择其中一个整数 a,将其变为 −a,并使圈上与其相邻的两个整数加上 a。
求至少操作几次,可以使所有整数均变为非负的。
输入格式
有多组测试数据。
第一行,一个正整数 T(1≤T≤10),表示测试数据组数。
对于每组测试数据,有两行:
- 第一行,一个正整数 n(3≤n≤105)。
- 第二行,n 个整数 a1,a2,⋯,an(−104≤ai≤104),这些整数按顺序排成一圈。
输出格式
对于每组测试数据,仅一行一个整数。如果能够使所有整数均变为非负的,输出最小的操作次数;如果不能,则输出 −1。
样例数据
样例输入
3
3
2 2 -3
3
2 2 -5
3
0 0 0
样例输出
5
-1
0
样例解释
初始 2,2,−3⟹−1,−1,3⟹1,−2,2⟹−1,2,0⟹1,1,−1⟹0,0,1 达到目标,操作次数为 5,且显然无法更优。
初始 2,2,−5,显然无法达到目标。
初始 0,0,0,无需操作即已经达到目标。
子任务
- 任务 1(10 分):n=3,−10≤ai≤10。
- 任务 2(20 分):n≤50,−10≤ai≤10。
- 任务 3(30 分):n≤2000。
- 任务 4(10 分):n≤3×104,∑ai=1
- 任务 5(10 分):n≤3×104,−10≤∑ai≤10。
- 任务 6(10 分):n≤3×104。
- 任务 7(10 分):无特殊条件。
对于 100% 的数据,1≤T≤10,3≤n≤105,−104≤ai≤104。