题目内容

某公司在 $n$ 个城市设有区域分仓，分仓沿一条环形物流干线布局——仓 $1$ 与仓 $2$ 相邻，仓 $2$ 与仓 $3$ 相邻，……，仓 $n$ 与仓 $1$ 相邻（首尾相接构成一个环）。

每个分仓 $i$ 需要补充 $a_i$ 件货物（$a_i$ 为非负整数）。总部通过“补货班次”完成补货：每个班次中，调度员选择一组分仓进行集中补货，被选中的分仓各补 $1$ 件货物。

由于环形干线上同一班次内相邻两个分仓同时补货会共用同一传送带从而产生调度冲突，因此每个班次选中的分仓集合必须是环上的独立集——即任何两个被选中的分仓在环上都不能相邻（注意仓 $1$ 与仓 $n$ 也是相邻的）。

每个班次耗时 $1$ 小时。每个分仓 $i$ 必须恰好被补货 $a_i$ 次。请你计算最少需要多少个班次才能完成全部补货任务。

输入描述

第一行一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行一个正整数 $n$ $(1 \le n \le 2 \times 10^5)$，表示分仓数量。
• 第二行 $n$ 个非负整数 $a_1,a_2,\dots,a_n$ $(0 \le a_i \le 10^9)$，其中 $a_i$ 表示分仓 $i$ 需要补货的件数。

输出描述

对于每组测试数据，输出一行一个整数，表示最少需要的班次数。

补充说明

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^6$。

样例1

输入

1
3
1 1 1

输出

3

说明

$(n=3)$，三个仓两两相邻（仓 $1$ 与仓 $2$、仓 $2$ 与仓 $3$、仓 $3$ 与仓 $1$ 都相邻），因此任意一个班次里至多只能选中 $1$ 个分仓补货。三个仓各需补 $1$ 件，无法合并到同一班次，故至少需要 $3$ 个班次。一种可行方案是：班次 $1$ 补仓 $1$，班次 $2$ 补仓 $2$，班次 $3$ 补仓 $3$。

样例2

输入

1
4
3 0 3 0

输出

3

说明

$(n=4)$，仓 $1$ 与仓 $3$ 不相邻、仓 $2$ 与仓 $4$ 不相邻，所以一个班次可以同时选中 $\{1,3\}$ 或 $\{2,4\}$。仓 $1$、仓 $3$ 各需 $3$ 件，仓 $2$、仓 $4$ 不需补货。每次都选 $\{1,3\}$ 同时补 $1$ 件，重复 $3$ 个班次即可完成全部补货；又因仓 $1$ 单独就需要 $3$ 次，不可能少于 $3$ 个班次，故答案为 $3$。

样例3

输入

1
6
1 2 3 1 2 3

输出

5

说明

$(n=6)$，环上相邻关系为 $1$-$2$-$3$-$4$-$5$-$6$-$1$。仓 $2$ 与仓 $3$ 相邻，二者不能在同一班次被同时补货，因此它们合计需要的 $(2+3=5)$ 次补货必须分散在 $5$ 个互不相同的班次中，所以班次不可能少于 $5$。另一方面，确实可以用 $5$ 个班次完成全部补货，例如：班次 $1$ 选 $\{2,5\}$，班次 $2$ 选 $\{3,6\}$，班次 $3$ 选 $\{3,6\}$，班次 $4$ 选 $\{1,3,5\}$，班次 $5$ 选 $\{2,4,6\}$（每个班次内的仓在环上两两不相邻，符合独立集要求）。累计仓 $1$ 补 $1$ 次、仓 $2$ 补 $2$ 次、仓 $3$ 补 $3$ 次、仓 $4$ 补 $1$ 次、仓 $5$ 补 $2$ 次、仓 $6$ 补 $3$ 次，恰好满足需求。故答案为 $5$。