题目描述
给定一个长度为 $n$ 的环状数列 $a_1,a_2,\cdots, a_n$，所谓环状，是指在考虑相邻关系时，需要把 $a_1$ 和 $a_n$ 也看做是一对邻居。
每个数字各自表示一堆物资的数量。我们希望从 $n$ 个位置中挑选一个位置，使得所有物资能聚集到一起，而且运费总和达到最小。
物资只能沿着相邻位置搬运，每当一单位物资移动一单位距离时，需要花费一单位运费。请问如何选择一个聚集点，使得运费总和达到最小？
输入
第一行：单个整数表示 $n$。
第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。
输出
单个整数：表示将所有物资移动到一起的最小总运费。
样例输入输出
提示
+ 对于 $30\%$ 的数据，$1\leq n\leq 100$；
+ 对于 $60\%$ 的数据，$1\leq n\leq 2000$；
+ 对于 $100\%$ 的数据，$1\leq n\leq 500,000$，
+ $0\leq a_i\leq 1,000,000$。
样例1说明:选择4作为聚集点，运费计算公式为1\*2+2\*2+3\*1+5\*1=14
选择5作为聚集点，运费计算公式为1\*1+2\*2+3\*2+4\*1=15