题目描述

有 $n$ 台服务器按环形排列，第 $i$ 台服务器当前承受的负载为非负整数 $a_i$。

Devin 希望通过降低负载，使所有服务器最终具有相同的负载，并让这个共同负载尽可能大。

他编写了一个有缺陷的脚本。对服务器 $i$ 执行一次脚本时：

• 服务器 $i$ 的负载减少 $2$，但不会低于 $0$；
• 环中服务器 $i$ 的前一台服务器的负载额外减少 $1$，同样不会低于 $0$。

当 $i=1$ 时，它的前一台服务器是服务器 $n$。

Devin 可以执行任意多次操作，也可以一次都不执行。每次可以任选一台服务器执行脚本。即使服务器 $i$ 当前负载小于 $2$，或它的前一台服务器负载已经为 $0$，仍然允许执行脚本；对应负载只会降到 $0$。

请计算所有服务器最终能够达到的最大相同负载。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 $n$；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

数据范围

所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示能够达到的最大相同负载。

样例

5
4
9 9 6 8
2
3 5
9
9 9 8 2 4 4 3 5 3
3
777 777 777
6
0 1 0 1 0 1

5
1
0
777
0

样例说明

在第一组测试中，可以对服务器 $1$ 执行一次脚本，对服务器 $2$ 执行两次，对服务器 $4$ 执行一次。最终每台服务器的负载均为 $5$。