A16791 | Greta's Game

Greta 与 Alice 是著名喜剧节目 “QuestExpert” 的两位常驻主持人。本季 Alice 邀请了 $n$ 位程序员完成由她设置的任务。随后，所有人齐聚演播室，回顾表现并参与最后的演播室挑战。

今天，Alice 制定的演播室挑战规则如下：首先，所有 $n$ 位参与者按 $1$ 到 $n$ 的顺序逆时针站成一圈。然后，Alice 进行若干轮游戏。每一轮中，每位参与者在纸上写下一个整数。之后，Alice 检查每个人写的数字，并且对于每个 $i$（$1 \leq i \leq n$），如果第 $i$ 位参与者写下的数字严格大于其逆时针下一个人的数字（即第 $(i \bmod n) + 1$ 位），那么第 $i$ 位和第 $(i \bmod n) + 1$ 位参与者各得 $1$ 分。所有轮次结束后，Alice 统计每位参与者的总得分并告知 Greta。结果是第 $i$ 位参与者获得了 $a_i$ 分。

Greta 觉得这种数学游戏有点无聊而且花了太久。为了证明游戏其实不长，Alice 决定“作弊”，她并不报告真实轮数，而是报告使每位参与者得分均为 $a_i$ 所需的最小轮数。

请你帮 Alice 计算这个最小轮数。

输入包含多个测试用例。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数量。

每个测试用例的第一行包含一个整数 $n$，表示参与者人数（$2 \leq n \leq 5 \times 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每位参与者的得分（$0 \leq a_i \leq 10^9$）。保证给定的得分序列可以通过上述游戏以至少一轮得到。

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

对于每个测试用例，输出一行，表示可能获得给定分数的最小轮数。