题目描述

题目译自 XXX Olimpiada Informatyczna – II etap Drwale

两位伐木工 Bajtek 和 Bitek 以相同速度砍伐 $n$ 块木材，初始堆放在一起。第 $i$ 块木材需耗时 $a_i$ 分钟。每次某位伐木工完成当前木材后，从堆顶取下一块。若两人同时完成，Bajtek 优先取木材。

你的任务是计算在最不利排列下，伐木工完成所有砍伐的最晚时间。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^6)$，表示木材数量。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每块木材的砍伐时间。

设 $A = a_1 + a_2 + \ldots + a_n$ 为总砍伐时间，满足 $A \leq 5000000$。

输出格式

输出一个整数，表示伐木工完成砍伐的最长可能时间。

样例

输入

3
2 3 1

输出

4

解释：
若木材按顺序 $1, 2, 3$ 排列（耗时 $1, 2, 3$），可达结果 $4$。Bajtek 先取木材 $1$（耗时 $1$），Bitek 取木材 $2$（耗时 $2$）。$1$ 分钟后，Bajtek 取木材 $3$（耗时 $3$）。$4$ 分钟后，所有木材砍伐完成。

附加样例

• $n=6$, $a_i = i$，答案为 $13$。
• $n=1000$, $a_i = 1$，答案为 $500$。
• $n=10$, $a_i = 2^{i-1}$，答案为 $767$。
• $n=2$, $a_i = 2500000$，答案为 $2500000$。

数据范围与提示

详细子任务附加限制及分值如下表所示。