题目描述

有 $n$ 个位置排成一行，编号为 $1$ 到 $n$。一只青蛙一开始站在第 $1$ 个位置，它想到达第 $n$ 个位置。

青蛙每次可以选择跳 $1$ 格或跳 $2$ 格，也就是可以从位置 $i$ 跳到位置 $i+1$ 或位置 $i+2$。如果目标位置超过 $n$，则不允许这样跳。

每个位置 $i$ 都有一个代价 $cost_i$。青蛙到达并停留在某个位置时，需要支付该位置的代价。第 $1$ 个位置作为起点需要支付代价，第 $n$ 个位置作为终点也需要支付代价。

求青蛙从第 $1$ 个位置到达第 $n$ 个位置所需支付的最小总代价。

输入格式

第一行包含一个整数 $n$，表示位置数量。

第二行包含 $n$ 个整数 $cost_1, cost_2, \cdots, cost_n$，表示每个位置的代价，相邻整数之间用一个空格分隔。

输出格式

输出一行一个整数，表示到达第 $n$ 个位置的最小总代价。

样例

5
1 3 2 4 5

8

样例说明

一种最优跳法是：

支付代价为：

因此最小总代价为 $8$。

数据范围与提示

对于 $30\%$ 的数据，$n \le 1000$。

对于 $100\%$ 的数据：

• $1 \le n \le 10^5$
• $0 \le cost_i \le 10^9$
• 答案可能较大，建议使用 64 位整数。
• 当 $n=1$ 时，青蛙已经在终点，只需支付 $cost_1$。