P6507 [CRCI2007-2008] NIKOLA

有一行 $n$ 个格子，编号为 $1\sim n$，Nikola 从 $1$ 号格子出发，想要前往 $n$ 号格子。 他的行程包含若干次跳跃，第一次只能跳到 $2$ 号格子，接下来的跳跃必须满足以下条件： - 如果他向 $n$ 号格子的方向跳跃，那么每次必须比前一次多跳一个距离的格子； - 如果他向 $1$ 号格子的方向跳跃，那么每次必须与上一次的跳跃距离完全相同。 例如，在第一次跳跃之后（位于 $2$ 号格），Nikola 可以选择跳到 $4$ 或者 $1$。 每进入一个格子，Nikola 都要支付相应的入场费。第 $i$ 个格子需要付费 $a_i$。他希望在能到达 $n$ 号格的前提下尽可能少的花钱。你需要求出这个最小值。

输入第一行一个整数 $n$，表示格子的数量。 接下来的 $n$ 行，每行一个整数 $a_i$，依次表示 $1\sim n$ 号格子的入场费。

输出一行一个整数，表示最小的花费。 **注意：刚开始所在的 $1$ 号格子不计费，但多次经过同一个格子需要计费。**

#### 样例 1 解释 在第一个样例中，Nikola 的路线为 $1-2-1-3-6$。共花费 $2+1+3+6=12$ 。 #### 数据规模与约定 对于 $100\%$ 的数据，保证 $2\le n\le 1000$，$1\le a_i\le 500$。 #### 说明 **题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [Regional Competition](https://hsin.hr/coci/archive/2007_2008/regional_tasks.pdf) *T2 NIKOLA***。