题目描述

题目背景

神灵庙的庭院，沐浴在透过古老樱树缝隙洒下的、斑驳陆离的阳光中。时光在这里似乎沉淀了下来，充满了静谧的古意。丰聪耳神子与物部布都相对而坐，中间是一张古朴的石制棋盘。棋盘上，黑白棋子交错，战局正酣。神子落子从容不迫，带着俯瞰全局的余裕；布都则眉头微蹙，每一步都深思熟虑，体现出军师的严谨。

苏我屠自古以灵体的姿态飘浮在一旁，她手中提着一个素雅的陶制茶壶，当任何一方的茶杯浅下去时，她便无声无息地为其续上温热的新茶。茶烟袅袅升起，带着淡淡的檀香和茶香，与庭院里的草木清气混合在一起。

棋盘上的厮杀虽是无声，却暗藏锋芒。神子偶尔会因布都的一步妙手而微微挑眉，嘴角勾起赞赏的弧度；布都则会因为神子看似随意、实则暗藏玄机的一子而陷入更长的思考。然而，她们口中所谈论的，却与这激烈的棋局毫无关系。

“今日的茶，用的是后山新采的初露，似乎比往常更甘洌一些。”神子端起茶杯，轻轻啜饮一口。

“是的，神子大人。今晨的雾气恰到好处，露水纯净。”布都暂时将目光从棋盘上移开，恭敬地回答。

“说起来，”屠自古的声音空灵地响起，“天空那朵云，像不像一只正在打哈欠的狛犬？”她指了指天空。

神子和布都都抬眼望去，只见一朵蓬松的白云正慢慢飘过，形状确实有几分憨态可掬。神子轻笑出声：“经你这么一说，倒真有几分神似。布都，你觉得呢？”

布都仔细看了看，严肃地点点头：“头部和蜷伏的躯干，确有形态。”

严肃的棋局，轻松的家常闲聊，古老庭院里的阳光与茶香，构成了一幅奇异而和谐的画面。在这里，她们是千年前的王者、军师与贵族，也是此刻享受宁静时光的、普通的友人与同居者。

题目描述

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

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

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

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

输入格式

第一行包含一个整数 \(t\) （\(1 \le t \le 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\) 还满足题目所示条件。