Johnny 的童子军小队正面临指挥结构的调整。小队共有 $n$ 名童子军，编号为 $1$ 到 $n$。指挥结构的定义如下：
- 指挥结构有一个指挥官。
- 编号小于其指挥官的童子军组成第一分队，编号大于其指挥官的童子军组成第二分队；其中一个或两个分队都可以为空。
- 非空的分队拥有它们自己的指挥结构。
- 一个队伍的指挥官是其子队伍指挥官的上司。
该指挥结构将用于传递一条非常重要的消息：消息从外部传达给某一位童子军，该童子军阅读后将其传递给他的上司；这一过程不断重复，直到消息到达整个队伍的监督者。不同的童子军阅读消息所需的时间不同：第 $i$ 位童子军需要 $a_i$ 的时间。处理消息所需的时间是所有传递过该消息的童子军（包括整个队伍的指挥官）阅读消息的时间总和。
不幸的是，目前尚不清楚哪位童子军会收到这条消息。Johnny 应该重新调整队伍的指挥结构，以最小化处理消息的最大可能时间。请帮助他。写一个程序，读取童子军的人数以及他们每个人阅读消息所需的时间，计算出处理消息的最小可能的最大时间，并将结果输出到标准输出。
输入格式
输入的第一行包含一个整数 $n$（$1 \le n \le 2\,000$）—— 童子军的人数。
输入的第二行包含对队伍的描述。它由 $n$ 个空格分隔的整数 $a_i$（$1 \le a_i \le 1\,000\,000\,000$）组成，表示对应童子军阅读消息所需的时间。
输出格式
你的程序应该输出一个整数 —— 处理消息的最小可能的最大时间。
样例
输入样例 1
5 6 2 4 7 4
输出样例 1
13
输入样例 2
5 1 2 1 2 1
输出样例 2
4
说明
在样例 1 中，最优的指挥结构如下图左侧所示。节点中的数字对应相应童子军的阅读时间。处理消息的最大时间为 13。
在样例 2 中，最优的指挥结构如上图右侧所示。节点中的数字对应相应童子军的阅读时间。处理消息的最大时间为 4。