题目描述

战国时期的魏国，最先实行变法，并以吴起为将训练魏国精兵“魏武卒”。由于在战场上通常是 $n$ 队士兵排成一列作战。在作战过程中，每隔一段时间，经常需要小队士兵合成一队，通常需要相邻队的士兵合成一队（如果不相邻合成一队那么阵型就乱了）。每队士兵人数不等，（合并后的士兵数即为合并之后队伍的消耗）。 请你帮吴起计算，$n$ 队士兵合成一队后，最小消耗是多少？

输入格式

输入一个整数 $n$，为 $n$ 队士兵。 接下来 $n$ 行，每行一个正整数，小于 $10000$，分别表示第 $i$ 队士兵的个数 $(1≤i≤N)$。

输出格式

输出最小消耗是多少？

7
13
7
8
16
21
4
18

239