1428: 七曜与链术士

异客在回萨尔贡的路上遇到了由 $n$ 个源石虫围成的圆，每一个源石虫的生命值为 $a_i$，异客决定消灭它们.

作为一名非常强大的术士, 异客掌握着一种强大的法术.

异客首先会选择法术的威力 $x$ 和第一个攻击的目标 $i$。

对当前目标造成伤害之后，法术会将其右边的源石虫 (第 $i + 1$ 个源石虫，第 $n$ 个源石虫的右边是第 $1$ 个源石虫)作为下一个目标，直到法术攻击过所有的源石虫一次。

每次攻击造成等同于当前法术威力的伤害，当一只源石虫的生命值小于等于法术的伤害时我们就认为这只源石虫死亡，每次攻击完一个目标之后法术的威力就会下降 $1$ 点。

异客只能释放一次这种法术，为了节约体力他想尽量使用最小的威力杀死这些源石虫，请问他最小可以选择的威力 $x$ 是多少.

第一行，一个整数 $t$ 代表样例用例数.

每组样例的第一行包含一个整数 $n$.

每组样例的第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$.

数据范围：

$1 \leq t \leq 10^5$

$1 \leq n  \leq 2*10^5$

$1 \leq a_i \leq 10^9$

保证所有测试用例的 $n$ 的总和不超过 $2*10^5$.

1
6
1 1 4 5 1 4

7