T827098 环线分区（district）

一条环形巡检线路由 $N$ 段道路首尾相接而成。按顺时针方向，这些道路依次编号为 $1,2,\ldots,N$，第 $i$ 段道路的长度为 $A_i$。第 $N$ 段道路之后是第 $1$ 段道路。 现在要在道路与道路之间的连接处设置三个不同的分界，将整条环线划分为三个巡检区域，分别交给三支队伍负责。每个区域都必须包含至少一段道路，并且由环线上连续的若干段道路组成。所有道路都必须恰好属于一个区域，不能把一段道路从中间分开。 一个区域的总长度等于其中所有道路的长度之和。为了让最短的区域也有足够的巡检工作，希望三个区域总长度的最小值尽可能大。 请你求出这个最小值最大可以是多少。各组数据相互独立。

第一行包含一个整数 $T$，表示数据组数。 对于每组数据： - 第一行包含一个整数 $N$，表示道路段数。 - 接下来 $N$ 行，第 $i$ 行包含一个整数 $A_i$，表示第 $i$ 段道路的长度。

对于每组数据，输出一行一个整数，表示三个区域总长度的最小值的最大可能值。

### 样例解释 可以将第 $1,2$ 段道路分为一个区域，第 $3,4$ 段道路分为一个区域，第 $5,6$ 段道路分为一个区域。这三个区域的总长度分别为 $1+5=6$、$4+5=9$、$2+4=6$，最小值为 $6$。 所有道路的总长度为 $21$。如果最短区域的总长度至少为 $7$，三个区域的总长度就必须都恰好为 $7$。但环线上总长度为 $7$ 的连续区域只有第 $4,5$ 段与第 $5,6,1$ 段，它们不能把全部道路分成三个互不重叠的区域。因此答案为 $6$。 ## 样例 2 见 `考生目录/district/district2.in` 与 `考生目录/district/district2.ans`。该样例满足测试点 $1$ 的约束。 ## 样例 3 见 `考生目录/district/district3.in` 与 `考生目录/district/district3.ans`。该样例满足测试点 $2\sim4$ 的约束。 ## 样例 4 见 `考生目录/district/district4.in` 与 `考生目录/district/district4.ans`。该样例满足测试点 $5\sim10$ 的约束。 ## 样例 5 见 `考生目录/district/district5.in` 与 `考生目录/district/district5.ans`。该样例满足测试点 $11\sim20$ 的约束。 ## 样例 6 见 `考生目录/district/district6.in` 与 `考生目录/district/district6.ans`。该样例满足测试点 $11\sim20$ 的约束。 ## 数据范围 对于所有数据，保证： - $1\le T\le10$； - 每组数据中，$3\le N\le10^5$，$1\le A_i\le10^9$； - 同一个输入文件中，所有数据的 $N$ 之和不超过 $2\times10^5$。 | 测试点编号 | 附加限制 | | :--------: | :------------------------------------------: | | $1$ | $N\le100$ | | $2\sim4$ | $N\le400$ | | $5\sim10$ | 每组 $N\le5000$，同一文件内 $\sum N\le20000$ | | $11\sim20$ | 无 |