题目描述

Nikola 现在已经成为一个游戏里的重要人物。这个游戏是由一行 N 个方格，N 个方格 用 1 到 N 的数字表示。Nikola 开始是在 1 号位置，然后能够跳到其他的位置，Nikola 的第 一跳必须跳到 2 号位置。随后的每一跳必须满足两个条件： 1、如果是向前跳，必须比前面一跳远一个方格。 2、如果是向后跳，必须和前面一跳一样远。 比如，在第一跳之后（当在 2 号位置时），Nikola 能够跳回 1 号位置，或者向前跳到 4 号位置。 每次他跳入一个位置，Nikola 必须付费。Nikola 的目标是从一号位置尽可能便宜地跳 到 N 号位置。 写一个程序，看看 Nikola 跳到 N 号位置时最小的花费。

输入格式

输入文件 nikola.in 共有 N+1 行。 第一行：包含一个整数 N，2≤N≤1000，它是位置的编号。 第 2..N+1 行：第 i+1 行表示第 I 个方格的费用，是一个正整数，绝对不超过 500。

输出格式

输出文件 nikola.out 中只有一个数，表示 Nikola 跳到 N 号位置时最小的花费。

样例 #1

样例输入 #1

6
1
2
3
4
5
6

样例输出 #1

12

样例 #2

样例输入 #2

8
2
3
4
3
1
6
1
4

样例输出 #2

14