问题描述

仔仔在玩一个打怪闯关的游戏。

这个游戏共有n个关卡，每个关卡都有怪物，仔仔通过关卡会消耗生命值，这里给出一个整数数组hp，其中hp[i]是仔仔通过关卡i消耗的生命值。

该游戏为了降低难度，允许玩家跳关，但是只能跳过一关，并且不能连续跳关。

仔仔希望你能帮忙计算一下他通关这款游戏扣除的生命值最少是多少。

为了简单起见，不考虑生命值不够游戏结束的情况。

格式

输入

总共两行 第一行为一个整数n，表示有多少个关卡 第二行为n个整数hp[i]​，表示通过第i个关卡消耗的生命值

输出

一个整数，表示通关这款游戏扣除的最少生命值。

样例

3
10 15 20

15

10
1 100 1 1 1 100 1 1 100 1

6

提示

样例说明1

仔仔跳过第一个关卡，然后消耗 $15$hp通过第二个关卡，最后跳过第三个关卡，通关。生命值消耗为 $15$ 。

样例说明2

仔仔消耗$1$生命值，通过关卡$1$，并跳过关卡$2$。 消耗 $1$ ，通过关卡$3$，并跳过关卡$4$。 消耗 $1$ ，通过关卡$5$，并跳过关卡$6$。 消耗 $1$ ，通过关卡$7$。 消耗 $1$ ，通过关卡$8$，并跳过关卡$9$。 消耗 $1$ ，通过关卡$10$，通关。

数据范围

$2 \leq n \leq 1000$ $0 \leq hp[i] \leq 999$