到达终点的最小费用

难度：T2

【知识点：一维动态规划】

前置知识：数组、循环、状态与转移。

题目描述

从第 $0$ 级地面出发，每次向上走 $1$ 级或 $2$ 级，必须恰好落在第 $n$ 级。每次落在第 $i$ 级支付非负费用 $c_i$；跨过该级无需支付，地面免费。求到达目标的最小总费用。目标台阶的费用也必须支付。

输入格式

第一行一个整数 $n$。第二行 $n$ 个整数 $c_1,\ldots,c_n$。

输出格式

一行一个整数，表示题目所求的最优总值。

样例输入

3
5 1 4

样例输出

5

样例解释

走 $0\to2\to3$，费用 $1+4=5$。

数据范围

$1\le n\le100000$，$0\le c_i\le10^9$。