CF2181G.Greta's Game

Greta and Alice are the two permanent hosts of the hit comedy show "QuestExpert". For this season they invited $n$ programmers to complete quests, set by Alice. After that they all meet in a studio to review how well they did and complete the final studio quest.

Today, the studio quest that Alice came up with is as follows: first, all $n$ participants stand in a circle in order from $1$ to $n$ counter-clockwise. Then Alice holds some number of rounds. In each round, every participant writes down an integer on a piece of paper. After that, Alice checks the numbers and for each $i$ from $1$ to $n$, if the $i$-th participant's number is strictly larger than the number of the next participant in counter-clockwise order (participant number $(i \bmod n) + 1$), then the $i$-th and the $(i \bmod n) + 1$-st participants both receive one point. After all rounds are complete, Alice calculates the total number of points for each participant and reports them to Greta. It turned out that the $i$-th participant scored $a_i$ points.

Greta thinks that math games are boring, and this one took too long. To prove her wrong, Alice decides to cheat a little and instead of telling Greta the real number of rounds, she will tell her the minimum possible number of rounds that could still result in the $i$-th participant scoring $a_i$ points for each $i$.

Help Alice determine this number.

格蕾塔和爱丽丝是热门喜剧节目《QuestExpert》的两位固定主持人。本季，她们邀请了 $n$ 名程序员来完成由爱丽丝设计的各项任务。之后，所有人齐聚演播室，回顾各自表现，并共同完成最终的演播室任务。

今天，爱丽丝设计的演播室任务如下：首先，所有 $n$ 名参与者按编号 $1$ 到 $n$ 逆时针方向围成一个圆圈。接着，爱丽丝主持若干轮游戏。在每一轮中，每位参与者都在纸上写下一个整数。随后，爱丽丝检查这些数字；对每个 $i$（从 $1$ 到 $n$），若第 $i$ 位参与者的数字严格大于其在逆时针方向上的下一位参与者（即编号为 $(i \bmod n) + 1$ 的参与者）所写的数字，则第 $i$ 位与第 $(i \bmod n) + 1$ 位参与者各得一分。待所有轮次结束后，爱丽丝统计每位参与者的总得分，并将结果告知格蕾塔。结果发现，第 $i$ 位参与者共获得 $a_i$ 分。

格蕾塔认为数学游戏枯燥乏味，且本次任务耗时过长。为了证明她错了，爱丽丝决定稍作“作弊”：她不告诉格蕾塔实际进行的轮数，而是告诉她——能够使得每位参与者 $i$ 恰好获得 $a_i$ 分的最少可能轮数。

请帮助爱丽丝确定这一最小轮数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$, denoting the number of participants ($2 \le n \le 5 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, denoting the final scores of the participants ($0 \le a_i \le 10^9$). It is guaranteed that those scores were achieved in the described game with at least one round.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output on a separate line the minimum number of rounds that could lead to the given scores.

对于每个测试用例，在单独一行输出能够得到给定分数的最少轮数。