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

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

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

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

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

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

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

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

样例 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 。

东方博宜OJ

月赛动态规划2023