← 返回题目列表

Codeforces · 2181/G

G. 格蕾塔的游戏

中文机器翻译题面 查看原题

格蕾塔和爱丽丝是热门喜剧节目“QuestExpert”的两位永久主持人。在这一季中,他们邀请了 $$$n$$$ 程序员来完成 Alice 设定的任务。之后,他们都会在工作室见面,回顾自己的表现并完成最终的工作室任务。

今天,Alice提出的工作室任务如下:首先,所有$$$n$$$参与者按照从$$$1$$$到$$$n$$$逆时针顺序站成一圈。然后爱丽丝持有一定数量的回合。在每一轮中,每个参与者在一张纸上写下一个整数。之后,Alice 检查号码,对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,如果第 $$$i$$$ 个参与者的号码严格大于逆时针顺序的下一个参与者的号码(参与者号码 $$$(i \bmod n) + 1$$$),则第 $$$i$$$ 和 $$$(i \bmod n) + 1$$$-st 参与者均获得一分。所有回合结束后,Alice 计算每个参与者的总得分并将其报告给 Greta。结果,第 $$$i$$$ 位参与者获得了 $$$a_i$$$ 分。

Greta 认为数学游戏很无聊,而且这个游戏花了太长时间。为了证明她的错误,Alice 决定作一点小作弊,她不会告诉 Greta 真实的轮数,而是告诉她仍然可以导致第 $$$i$$$ 参与者为每个 $$$i$$$ 获得 $$$a_i$$$ 分的最小可能轮数。

帮助 Alice 确定这个数字。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$,表示参与者的数量 ($$$2 \le n \le 5 \cdot 10^5$$$)。

第二行包含$$$n$$$整数$$$a_1, a_2, \ldots, a_n$$$,表示参与者的最终分数($$$0 \le a_i \le 10^9$$$)。保证这些分数是在所描述的游戏中至少一轮获得的。

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

输出

对于每个测试用例,在单独的行上输出可能导致给定分数的最小轮数。

示例

输入
复制

5
2
3 3
3
2 2 2
4
1 2 4 3
5
0 2 3 5 4
6
5 8 3 10 14 4

输出
复制

3
2
2
4
10