题目描述

有一行 $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$ 号格子不计费，但多次经过同一个格子需要计费。

6
1
2
3
4
5
6

12

8
2
3
4
3
1
6
1
4

14

提示

样例 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 Regional Competition T2 NIKOLA。