Description

Greta 和 Alice 是热门喜剧节目“QuestExpert”的两位常驻主持人。在本季中，他们邀请了 $n$ 位程序员来完成由 Alice 设置的挑战。之后，他们齐聚演播室，回顾各自的表现并完成最终的演播室挑战。

今天，Alice 设计的演播室挑战如下：首先，所有 $n$ 位参与者按 $1$ 到 $n$ 的顺序逆时针站成一个圆圈。然后，Alice 主持若干轮。在每一轮中，每位参与者在一张纸上写下一个整数。之后，Alice 检查这些数字，对于每个从 $1$ 到 $n$ 的 $i$，如果第 $i$ 位参与者的数字严格大于下一位逆时针方向参与者（编号为 $(i \bmod n) + 1$ 的参与者）的数字，那么第 $i$ 位和第 $(i \bmod n) + 1$ 位参与者各自获得 $1$ 分。所有轮次结束后，Alice 计算每位参与者的总得分并报告给 Greta。结果显示，第 $i$ 位参与者获得了 $a_i$ 分。

Greta 认为数学游戏很无聊，而且这个游戏耗时太长。为了证明她错了，Alice 决定稍微作弊一下：她不告诉 Greta 真实的轮数，而是告诉她仍然能够使每位参与者 $i$ 获得 $a_i$ 分的最小可能轮数。

请帮助 Alice 确定这个数字。

Input Format

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

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

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

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

Output Format

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

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

Hint

翻译由 DeepSeek V3 完成