N个格子排成一排，编号从1到N，最初某人在格子1，第一步，他可以跳到格子2，且只能跳到格子2，接下来每一步他按如下规则进行：
1．如果向前跳，他必须比前一次多跳一格。
2.如果向后跳，且必须跳前一次一样多的格数。
例如：第一步跳了后，他可以向后跳到1或向前跳到4.
每进入一个格子，他必须给过路费，现在他的目标是从1到N，请给出最少的费用。
输入：
第一行一个整数N, 2 ≤ N ≤ 1000,表示方格的个数。
接下来N行，每行一个整数，依次表示每个格子要付的费用（均为小于500的正整数）
输出：
一个数表示最小费用。
样例：
输入：
6
1
2
3
4
5
6
输出：
12
输入：
8
2
3
4
3
1
6
1
4
输出：
14
I第一个样例中，第一步跳到第2格，接下来跳到第一格，接下来第3格，最后第6格。