【Background】

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

【Input】

输入共有 N+1 行。 第一行：包含一个整数 N，2≤N≤1000，表示格子的数量。 随后N行：第 i 行表示第 i 个方格的费用$w_i$，0 ≤ $w_i$ ≤ 500。

【Output】

输出只有一个数，表示 石老师 跳到 N 号位置时最小的花费。

【Samples】

6
1
2
3
4
5
6

12

8
2
3
4
3
1
6
1
4

14

Limitation

1s, 1024KiB for each test case.