该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有一种跳棋只需要一个人就可以玩，它是一个 1*N 的棋盘，棋盘依次用 1~N 标号。一开 始有一个棋子在 1 这个位置：

第一步，棋子只可以移动到 2 这个位置； 接下来每一步，棋子可以选择前进，前进的步数为上一次步数+1；或者后退，后退的步数 ， 必须等于上一次步数。

比如说，第二步走到 2 这个位置，那么第三步可以选择回到 1 或者前进到 4。 跳棋的目标就是跳到第 N 格，然后我们将沿途经过的所有格子的值加起来(一个格子经过多 次，则代价算多次)，使得这个值的和最小。

现在你有一副大小为 N 的棋，希望你给出这个最小的和。

Format

Input

第一行一个数 N，表示棋盘的大小。

接下来 N 行，每行一个正整数，依次描述每一格的值。

Output

一行一个数，表示最小的和。

Samples

6
1
2
3
4
5
6

12

Limitation

对于 60%的数据 N<=200；

对于 100%的数据 2<=N<=1000，每个格子的值不超过 500。

对于样例：1->2->1->3->6