吴起练兵

题目描述

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

请你帮吴起计算，$n$ 队士兵合成一队后，最小消耗是多少？

输入格式

输入一个整数 $n$，为 $n$ 队士兵。

接下来 $n$ 行，每行一个正整数，小于 $10000$，分别表示第 $i$ 队士兵的个数（$1 \le i \le N$）。

输出格式

输出最小消耗是多少？

样例输入 #1

7
13
7
8
16
21
4
18

样例输出 #1

239

数据范围

$2 \le N \le 100$

• 时间限制：1000MS
• 内存限制：128MB

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐（Mid+）。

测试点分布