当前没有测试数据。

题目描述

某城市计划沿着一条笔直的街道修建花圃。街道长度为 $N$ 米，从左到右编号为 $1$ 到 $N$。城市规划师需要在这条街道上选择若干个位置种植花卉，每个位置的花卉种植费用不同。

具体来说：

• 在位置 $i$ 种植花卉的费用为 $C_i$ 元
• 为了美观，相邻的位置不能同时种植花卉
• 城市希望选择若干个位置种植花卉，使得总费用最小

请帮助城市规划师计算最小的种植费用。

输入格式

第一行输入一个整数 $N$，表示街道长度。

第二行输入 $N$ 个整数，表示每个位置的种植费用 $C_1, C_2, …, C_N$。

输出格式

输出一个整数，表示最小的种植费用。

样例 #1

输入

5
1 2 3 4 5

输出

6

数据范围

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le C_i \le 10^4$。