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.

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 $ .

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