思路：动态规划

斐波那契的变种。

题目描述

有 $n$ 个格子，小红初始在 $1$ 号格子，想要跳到 $n$ 号格子。

小红每次可以往前跳一步或者两步（即从 $i$ 跳到 $i+1$ 或者 $i+2$），但是需要保证不能跳出 $n$ 个格子，即跳到的位置不能大于 $n$ 。到达 $i(1\leq i\leq n)$ 号格子需要缴纳 $a_i$ 的费用。

问小红到达 $n$ 号格子最少需要缴纳多少费用。

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$，表示格子的长度。
第二行，$n$ 个整数，第 $i$ 个整数为 $a_i(1 \leq a_i \leq 10^3)$ 。

数据保证 $a_1=a_n=0$ 。

输出描述

一个非负整数，表示小红到达 $n$ 号格子最少需要缴纳的费用。

样例

输入

5
0 1 2 3 0

输出

2

说明

从 1 号点跳到 3 号点，再从 3 号点跳到 5 号点，最少需要缴纳费用为 2 。