题目描述

小明在探险途中遇到了一座高耸的仙塔，他想从塔底爬到塔顶。

仙塔共有 $n$ 层，第 $i$ 层的高度为 $h_i$。小明初始时位于地面（第 $0$ 层），他每爬上一层就花费等于该层高度的时间。小明掌握一种仙术，每使用一次可以让他不花时间地向上跳过一层或两层，但每次使用仙术后，他必须至少正常爬上一层来恢复体力，然后才能再次使用仙术。

请帮小明计算到达塔顶（第 $n$ 层）所需的最短时间。

输入格式

第一行一个整数 $n$，表示仙塔的层数。

第二行 $n$ 个整数 $h_i$，表示从下往上第 $i$ 层的高度。

输出格式

一行一个整数 $t$，表示小明到达塔顶所需的最短时间。

样例

5
3 5 1 8 4

1

提示

对于所有的数据，保证 $1 \le n \le 10^6$，$1 \le h_i \le 100$。