题目描述
小爱在野外探险的时候，被 $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\leq a_i\leq 10^5$；
+ 对于 $30\%$ 的数据，$1\leq n\leq 20$；
+ 对于 $100\%$ 的数据，$1\leq n\leq 500$；
样例1说明:6+5+4+2+1