题目描述

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.

输入格式

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, \dots, 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$.

输出格式

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

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