圆环选址
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个长度为 nn 的环状数列 a_1,a_2,\cdots, a_na1,a2,⋯,an，所谓环状，是指在考虑相邻关系时，需要把 a_1a1 和 a_nan 也看做是一对邻居。
每个数字各自表示一堆物资的数量。我们希望从 nn 个位置中挑选一个位置，使得所有物资能聚集到一起，而且运费总和达到最小。
物资只能沿着相邻位置搬运，每当一单位物资移动一单位距离时，需要花费一单位运费。请问如何选择一个聚集点，使得运费总和达到最小？
输入格式
第一行：单个整数表示 nn。
第二行：nn 个整数表示 a_1, a_2, \cdots, a_na1,a2,⋯,an。
输出格式
单个整数：表示将所有物资移动到一起的最小总运费。
数据范围
对于 30%30% 的数据，1\leq n\leq 1001≤n≤100；
对于 60%60% 的数据，1\leq n\leq 20001≤n≤2000；
对于 100%100% 的数据，1\leq n\leq 500,0001≤n≤500,000，
0\leq a_i\leq 1,000,0000≤ai≤1,000,000。
样例数据
输入:
5
1 2 3 4 5
输出:
14
说明:
选择4作为聚集点，运费计算公式为12+22+31+51=14
选择5作为聚集点，运费计算公式为11+22+32+41=15