Problem A: 爬楼梯游戏II

Problem A: 爬楼梯游戏II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 960  Solved: 309
[Submit] [Status] [Web Board] [Creator:]

Description

现有n阶楼梯,PIPI从平地开始走到楼顶(共n阶楼梯,楼顶可视为第n+1阶),每次可以跨一阶或者两阶,走到第 i 阶楼梯对应的花费为 w[i]。现在PIPI想知道他走到楼顶的最小花费是多少。

Input

输入包含多组测试样例(组数不超过十组)。
接下来输入一个正整数n代表楼梯的阶数(1<=n<=1e5)。
接下来输入每一阶楼梯所需要的花费w[i] (0<=w[i]<=1e5)。

Output

对于每组测试样例,输出PIPI从第0阶到楼顶所需的最小花费。

Sample Input

4
1 2 3 4

Sample Output

4

HINT

  先跨一步到第1阶,花费1,再跨两步到第3阶,花费3,再从第三阶跨两步直接到楼顶。