最便宜的落点

难度：T4

【知识点：从暴力递归建立DP状态】

前置知识：从暴力递归建立DP状态及其冻结前置单元。

题目描述与输入

输入$n$以及位置$1$..$n$的落点费用。起点$0$免费，每次向前走$1$或$2$格，到达$n$。

输出

输出最小总费用。

数据范围

$0$<=$n<=2000$；落点费用绝对值<=$10^6$。

样例输入

4
4 1 7 2

样例输出

3

样例说明

按最后一步划分到达方式，状态是恰好到位置$i$。请按输入操作顺序逐步核对；没有规定输出的更新操作不输出额外内容。