小z的数

小z有n个数，分别为$a[1],a[2]...a[n]$.现在他把这n个数告诉了你并向你询问q次。

每次询问给定一个$l$，你需要找出最大的$r$使得$a[l]+a[l+1]+...+a[r]>=0$

第一行一个整数T，代表T组数组(T ≤ 10)

对于每组数据:

第一行一个整数$n(1 ≤n ≤ 100000)$

第二行$n$个整数分别为$a[1],a[2]...a[n].(-10^9 ≤ a[i] ≤ 10^9)$

第三行一个整数$q(1 ≤ q ≤ 100000)$

接下来每行一个整数$l$代表询问。

题目保证所有的n,q的和小于等于200000

$q$行每行一个整数代表答案，若$r$不存在，则输出-1。

1
4
2 1 3 -5
4
1
2
3
4

4
3
3
-1

2021杭州电子科技大学计算机学院Debug杯程序设计竞赛