题目描述

有 $n$ 个整数 $a_1,a_2,\dots,a_n$，按顺时针围成一个环。已知它们的和是 $0$。

你需要选择一个起始位置 $k$，从 $a_k$ 开始沿顺时针方向取连续 $n$ 个数，它们的所有前缀和都大于等于 $0$。

可以证明这样的 $k$ 一定存在。如果有多个满足条件的 $k$，请输出最小的那个。

换句话说，你需要寻找最小 $k$ （$1\le k \le n$），使得对所有 $l$（$0 \le l \le n−1$），都满足 $\sum_{i=0}^{n-1} a_{k+i} \ge 0$，其中 $a_{n+1}=a_1,a_{n+2}=a_2,\cdots ,a_{2n−1}=a_{n−1}$，保证 $\sum_{i=1}^n a_i=0$ 。

输入描述

第一行包含一个整数 $t$（$1≤t≤3000$），表示测试用例的数量。

接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行，包含一个整数 $n$（$1 \le n \le 2\times 10^5$）。

每个测试用例的第二行，包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$（$−10^9 \le a_i \le 10^9$），表示数组中的元素。

保证所有测试用例中 $n$ 的总和不超过 $5\times 10^5$。

输出描述

对于每个测试用例，输出一行，一个整数 $k$，使其满足题目中给定的条件。

样例

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

5
1

样例解释

在样例测试用例 1 中，$k=5$ 满足题目条件，因为 $a_5=2$，$a_5+a_6=5$，$a_5+a_6+a_7=4$，$a_5+a_6+a_7+a_8=2$，$a_5+a_6+a_7+a_8+a_9=0$ 均为非负数。可以证明，没有比 $5$ 更小的下标 $k$ 还满足题目所示条件。