题目描述

给定一个长度为 $n+1$ 的数组 $cost$ ，数组元素的编号为 $0 \sim n$ ，其中 $cost[i]$ 是从楼梯上编号为 $i$ 的台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

请找出达到楼层顶部的最低花费 (是要到达楼层顶部哦，不是第 $n$ 级台阶)。在开始时，你可以选择从编号为 $0$ 或 $1$ 的台阶作为出发的起点。

输入格式

第一行输入一个整数 $n$

第二行输入 $n+1$ 个整数

输出一个整数代表最低花费

2
10 15 20

9
1 100 1 1 1 100 1 1 100 1

样例 $1$ 从台阶 $1$ 开始，向上走两级台阶即可到达顶部，花费为 $15$

样例 $2$ 从台阶 $0$ 开始，一次经过台阶 $2$ , $4$ , $6$ , $7$ , $9$ 然后即可到达顶部，花费为 $6$ ，具体解释如下：

台阶0 \to 台阶2 \ \ \ 花费 1

台阶2 \to 台阶4 \ \ \ 花费 1

台阶4 \to 台阶6 \ \ \ 花费 1

台阶6 \to 台阶7 \ \ \ 花费 1

台阶7 \to 台阶9 \ \ \ 花费 1

台阶9 \to 顶部 \ \ \ 花费 1

对于 $100\%$ 的数据， $1 \leq n \leq 10^3$ , $0 \leq cost_{i} \leq 10^4$