Byteman 负责一个寻找原油储层的团队。他钻了两个孔：在点 $A$ 发现了原油，在点 $B$ 没有发现原油。已知油层占据了线段 $AB$ 的一个连通片段，且其中一端位于点 $A$。现在 Byteman 需要检查油层沿连接 $A$ 和 $B$ 的线段延伸到了多远。然而，这并不简单，因为在某些位置钻探的速度比其他位置快。此外，Byteman 的团队规模较小，因此他们一次最多只能在一个位置钻探。Byteman 的老板希望他能预先确定何时能够确定油层的边界。

Byteman 向你寻求帮助。他将连接 $A$ 和 $B$ 的线段分成了 $n+1$ 个等长的线段。如果我们假设点 $A$ 的坐标为 0，点 $B$ 的坐标为 $n+1$，那么它们之间有 $n$ 个坐标分别为 $1, 2, \dots, n$ 的点。只需找到这些点中距离 $A$ 最远且有原油的点即可。Byteman 告知了你在这些点进行钻探所需的时间，分别为 $t_1, t_2, \dots, t_n$。你需要制定一个钻探计划，使得在最坏情况下确定油层边界所需的时间尽可能短。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 2000$)。第二行包含 $n$ 个正整数 $t_1, t_2, \dots, t_n$，由空格分隔 ($1 \le t_i \le 10^6$)。

输出格式

你的程序应输出一个整数，表示 Byteman 为确定油层边界（假设最坏情况）所需花费的最短钻探时间。

样例

输入 1

4
8 24 12 6

输出 1

42

说明

假设 Byteman 首先在点 1 钻孔，耗时 8。之后可能会发现那里有原油，他将不得不检查油层向右延伸到了多远。他还需要再钻两个孔，在最坏情况下需要 36 个单位时间。因此，在这种情况下，Byteman 总共将花费 44 个单位时间进行钻探。

事实证明，从点 2 开始更好。如果那里没有原油，只需检查点 1 即可。然而，在最坏情况下，Byteman 将不得不继续在点 3 和点 4 钻孔，最终总耗时为 42。