狼群

题目描述

小爱在野外探险的时候，被 $n$ 头狼包围了。她需要消灭所有的狼。每一回合，她只能消灭一头狼，每消灭一头狼，所承受的伤害等于这头狼的攻击力。

每头狼的基本攻击力都是 $1$，但每头狼都对它的邻居都有攻击力加成。第 $i$ 头狼对邻居的加成为 $a_i$。

例如，在一开始，$3$ 号狼的实际攻击力为 $1 + a_2 + a_4$，因为它的基本攻击力为 $1$，左右的加成分别为 $a_2$ 与 $a_4$，若先消灭 $4$ 号狼，则 $3$ 号狼与 $5$ 号狼会成为新邻居，$3$ 号狼的实际攻击力将变为 $1 + a_2 + a_5$。

注意，由于狼群是圆形的，所以第一头狼与最后一头狼也是邻居关系。若最后只剩两头狼，每头狼对另一头狼的攻击力只加成一次。

小爱应该按照什么顺序消灭这些狼，才能使伤害总和最小呢？

输入格式

第一行：单个整数表示 $n$； 第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。

输出格式

输出一个整数表示答案。

数据范围

$1 \le a_i \le 10^5$； 对于 30% 的数据，$1 \le n \le 20$； 对于 100% 的数据，$1 \le n \le 500$。

样例输入

5
1 2 3 4 5

样例输出

18

说明：$6 + 5 + 4 + 2 + 1$

知识点与难度

本题涉及的知识点从属于 GESP六级（区间动态规划、破环为链），难度等级：⭐⭐⭐⭐。

测试点分布