题目描述

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

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

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

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

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

输入格式

第 $1$ 行读入整数 $N$，代表楼的层数。

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

输出格式

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

样例输入 #1

5
4 5 2 3 8

样例输出 #1

2

样例输入 #2

6
8 1 9 10 2 5

样例输出 #2

3

样例 $1$ 说明

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

数据范围

对 $20\%$ 的数据，$n \le 10$ 。

对 $40\%$ 的数据，$n \le 100$ 。

对 $60\%$ 的数据，$n \le 5000$ 。

对 $100\%$ 的数据，$3 \le n \le 10000$，$1 \le A_i \le 100$ 。