You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

你是一名探险家，计划穿越一片沙漠。沙漠被划分为连续的 N 个区域（1<=N<=40），每个区域都有一个沙丘。翻越沙丘 i 需要消耗 energy_i (0<=energy_i<=999) 单位的能量。你每次可以选择翻越 1 个沙丘 或 2 个沙丘（即直接跳过下一个沙丘）。注意： 从沙漠起点（沙丘 1 之前）出发，最终必须到达沙漠尽头（最后一个沙丘之后的位置 N+1）。 只有当你 踏上某个沙丘 时，才需要支付该沙丘的能量。 翻越过程中，你可以选择从沙丘 1 或沙丘 2 开始（即第一步可直接到达沙丘 2，跳过沙丘 1）。 现在请你计算穿越沙漠的最小总能量消耗。

Input

数据的第 1 行是正整数 N，表示有 N 个沙丘。 第 2 行有 N 个整数，第 i 个整数energy_i 表示第 i 个沙丘支付的能量。 。

Output

一个整数，表示最小总能量消耗

Samples

3
10 15 20

15

样例解释

解释: 第一步可直接到达沙丘 2（消耗 15 能量），然后翻越 2 个沙丘到达终点（跳过沙丘 2，不再消耗能量）。 总消耗为 15（路径：起点 → 沙丘 2 → 终点）。