题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。你需要支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 1 或下标为 2 的台阶开始爬楼梯。

请你计算达到楼梯顶部第n+1个台阶的最低花费。

输入格式

第一行一个整数 $n$。 接下来一行 $n$ 个正整数，分别表示每个台阶的花费cost[i]。

输出格式

一行一个整数，表示达到楼梯顶部的最小花费。

3
10 15 20

15

10
1 100 1 1 1 100 1 1 100 1

6

数据规模与约定

对于 $100\%$ 的数据，$1 < n \le 10^3$，输入的 $n$ 个正整数均小于 $1000$。

说明

样例一表示从台阶2开始，支付15的费用，向上爬两个台阶，到达楼梯顶部。总花费为15。