暂无测试数据。

开学了，蒜头君去领书处搬书，可是要把这 $n$ 本书搬回教室家一件很困难的事。具体来说，如果蒜头君一次搬运 $i$ 本书，就要花费 $a_i$ 的体力（显而易见，有 $a_i<a_{i+1}$，搬得越多耗费体力越多）。蒜头君并不在意他会搬多少次，但是他想知道，自己最少花费多少体力，就可以把这些书都搬回教室。

输入格式

第一行一个整数 $n\ (1\le n\le 5000)$。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i\ (1\le a_ i \le 50000)$ 表示蒜头君一次搬 $i$ 本书花费的体力。

数据保证 $a_i<a_{i+i}$。

输出格式

一个整数，表示蒜头君搬 $n$ 本书最少耗费的体力。

3
2 3 7

5