小红正在进行一次体能训练,场地上依次铺设了 块地砖,按照从 到 依次编号。她站在第 块地砖上,目标是走到第 块地砖。 已知走到第 块地砖需要消耗 的体力值。每一次移动,小红可以选择: 向前走 步,即从当前地砖 走到地砖 ; 向前走 步,即从当前地砖 走到地砖 。 请你帮助小红计算,从第 块地砖走到第 块地砖所需消耗的最小体力值。
输入描述:
第一行输入一个整数 ,表示地砖的数量。 第二行输入 个整数 ,其中 表示走到第 块地砖需要消耗的体力值。保证 。


输出描述:
在一行上输出一个整数,代表从第 块地砖走到第 块地砖所需消耗的最小体力值。
示例1

输入

5
0 3 2 1 0

输出

2

说明

\hspace{15pt}对于第一组样例: 
\hspace{23pt}\bullet\,一种最优走法为 1\rightarrow 3\rightarrow 5,实际经过的地砖编号为 \{1,3,5\}
\hspace{23pt}\bullet\,对应消耗的体力值为 a_1+a_3+a_5=0+2+0=2,无法再更小。
示例2

输入

6
0 1 0 2 1 0

输出

1

说明

\hspace{15pt}对于第二组样例: 
\hspace{23pt}\bullet\,一种最优走法为 1\rightarrow 3\rightarrow 5\rightarrow 6
\hspace{23pt}\bullet\,对应消耗的体力值为 a_1+a_3+a_5+a_6=0+0+1+0=1
加载中...