Description

Devin 是一家科技公司的系统管理员，负责管理由 $n$ 台服务器组成的环形拓扑网络。每台服务器当前承载的计算负载用一个非负整数 $a_i$ 表示，其中 $i$ 的取值范围是 $1$ 到 $n$。

为了优化网络性能并确保公平性，Devin 希望均衡所有服务器的负载，使每台服务器承担相同的工作量。他的目标是尽可能最大化这个均衡后的负载值。

Devin 开发了一个脚本来减少服务器的负载。当在服务器 $i$ 上运行该脚本时，理论上应该将该服务器的负载减少 $2$ 个单位（最低减至零）。但由于脚本中存在已知缺陷，每次在服务器 $i$ 上执行时，还会意外地使网络中前一台服务器（服务器 $i-1$）的负载减少 $1$ 个单位。如果 $i = 1$，则前一台服务器是服务器 $n$（因为服务器构成环形拓扑）。

Devin 可以任意次数（包括零次）运行这个有缺陷的脚本，每次可以选择任意服务器执行。即使某台服务器当前负载不足 $2$ 个单位，或者前一台服务器的负载为零，仍然可以运行脚本（在这两种情况下负载都会降至零）。

请帮助 Devin 确定使用该脚本后，所有服务器能够达到的最大可能均衡负载值。

Input Format

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

每个测试用例的第一行包含一个整数 $n$，表示服务器数量（$2 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示各服务器当前承载的负载值（$0 \le a_i \le 10^9$）。

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

Output Format

对于每个测试用例，输出所有服务器能够达到的最大可能均衡负载值。

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

Hint

在第一个测试用例中，Devin 可以在服务器 $1$ 上运行脚本 $1$ 次，服务器 $2$ 上运行 $2$ 次，服务器 $4$ 上运行 $1$ 次。最终每台服务器都将承担 $5$ 个单位的负载。