两位伐木工（Bajtek 和 Bitek）以相同的速度劈砍 $n$ 块木头，这些木头最初堆成一堆。劈砍第 $i$ 块木头需要 $a_i$ 分钟。每当其中一名伐木工劈完当前木头时，他就会从堆中取出下一块木头。如果两人同时劈完，Bajtek 会优先取出下一块木头。
请计算在木头堆放顺序极其不利的情况下，劈完所有木头所需的最晚结束时间。
输入格式
输入的第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示木头的数量。第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示劈砍每块木头所需的时间。
令 $A = a_1 + a_2 + \dots + a_n$ 表示劈砍的总时间。满足不等式 $A \le 5\,000\,000$。
输出格式
输出一行一个整数，表示伐木工工作的最长可能时间。
样例
输入格式 1
3 2 3 1
输出格式 1
4
说明
如果木头的顺序为 $1, 2, 3$，则可以达到结果 $4$。此时 Bajtek 开始劈第 $1$ 块木头，Bitek 从第 $2$ 块开始。$1$ 分钟后，Bajtek 取走第 $3$ 块木头，最终在 $4$ 分钟后所有木头都被劈完。
子任务
| 子任务 | 限制 | 分值 |
|---|---|---|
| 1 | $n \le 10$ | 5 |
| 2 | $A \le 500$ | 15 |
| 3 | $A \le 10\,000$ | 20 |
| 4 | $A \le 100\,000$ | 20 |
| 5 | $A \le 1\,000\,000$ | 20 |
| 6 | 无额外限制 | 20 |