该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目：跳跃

题目描述

蚂蚁军团收到来自一栋高楼楼顶的友军求助信号，他们必须以最短的时间赶到楼顶，增援友军。首领带领军团乘坐飞船开始增援。

这栋楼由于经过蚁国战争的洗礼，不同的楼层受到了不同程度的破坏，因此不同楼层的飞行时间有所不同，飞船飞跃第 $i$ 层楼所需的时间为 $A_i$。

蚂蚁军团的科学家，已经研发出了飞船的空间跳跃模块，飞船每次开启空间跳跃，都可以不费吹灰之力瞬间向上跳跃 1 层或者 2 层，跳跃不需要消耗任何时间。

不过这个科技还不够成熟，每次跳跃之后，必须停下来，把空间跳跃模块修整一下，才能再次开启跳跃。由于时间紧张，首领决定，每次跳跃之后修整时，立刻打开飞船的推进器，让飞船向上飞行一个楼层的距离，然后再次开启空间跳跃模块向上跳跃。

现已知 $N$ 层楼，每层楼飞行所需要的时间，请编程计算出飞船从楼底 飞行到楼顶（最高层上一层的屋面上），最少需要的飞行时间。

输入格式

第 1 行读入整数 $N$，代表楼的层数。
第 2 行读入 $N$ 个整数，第 $i$ 个整数 $A_i$ 代表飞船飞跃第 $i$ 层楼所需要的时间。

输出格式

输出一个整数，代表最短的飞行时间。

样例

样例 1

• 输入

5  
4 5 2 3 8  

• 输出

2  

• 样例 1 说明
  共有 5 层楼，从楼底先开启跳跃模块，跳跃到 3 楼，然后开启飞行器飞跃 3 楼需要的时间为 2，然后再次开启跳跃模块，跳跃到 5 楼(顶楼)的屋顶。

样例 2

• 输入

6  
8 1 9 10 2 5  

• 输出

3  

数据范围

• 对 20% 的数据， $n \leq 10$。
• 对 40% 的数据， $n \leq 100$。
• 对 60% 的数据， $n \leq 5000$。
• 对 100% 的数据， $3 \leq n \leq 10000$， $1 \leq A_i \leq 100$。