题目描述

小爱在野外探险的时候，被 $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$；

输出格式

输出一个整数表示答案。

5
1 2 3 4 5

18

样例解释 1

6+5+4+2+1

数据范围

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