题目描述

$\red{Nikola }$现在已经成为一个游戏里的重要人物。这个游戏是由一行 $\red{N }$个方格，$\red{N }$个方格 用 $\red{1 }$到 $\red{N }$的数字表示。

$\red{Nikola }$开始是在 $\red{1 }$号位置，然后能够跳到其他的位置，$\red{Nikola }$的第 一跳必须跳到 $\red{2 }$号位置。随后的每一跳必须满足两个条件：

$\red{1}$、如果是向前跳，必须比前面一跳远一个方格。

$\red{2}$、如果是向后跳，必须和前面一跳一样远。

比如，在第一跳之后（当在 $\red{2 }$号位置时），$\red{Nikola }$能够跳回 $\red{1 }$号位置，或者向前跳到 $\red{4}$ 号位置。

每次他跳入一个位置，$\red{Nikola }$必须付费。$\red{Nikola }$的目标是从一号位置旧能便宜地跳 到 $\red{N }$号位置。

写一个程序，看看 $\red{Nikola }$跳到 $\red{N }$号位置时最小的花费。

输入格式

输入文件 $\red{nikola.in }$共有 $\red{N+1 }$行。

第一行：包含一个整数 $\red{N，}$$\red{2≤}$$\red{N≤}$$\red{1000，}$它是位置的编号。

第 $\red{2..N+1 }$行：第 $\red{i+1 }$行表示第 $\red{I }$个方格的费用，是一个正整数，绝对不超过 $\red{500}$。

输出格式

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

样例

输入样例1

6
1
2
3
4
5
6

输出样例1

12

输入样例2

8
2
3
4
3
1
6
1
4

输出样例2

14