题目描述

给定一个长度为 n 的环状数列 a1​,a2​,⋯,an​，所谓环状，是指在考虑相邻关系时，需要把 a1​ 和 an​ 也看做是一对邻居。

数列的每个位置上都有一堆物资，数列上的每个数字表示该堆物资的数量。我们希望从 n 个位置中挑选一个位置，使得所有物资能聚集到一起，而且运费总和达到最小。

物资只能沿着相邻位置搬运，每当一个单位物资的移动一个单位距离时，需要支付一个单位的运费。请问如何选择一个聚集点，使得运费总和达到最小？

输入格式

第一行：单个整数表示 n。 第二行：n 个整数表示 a1​,a2​,⋯,an​。

输出格式

单个整数：表示将所有物资移动到一起的最小总运费。

数据范围

样例数据

 输入: 5 1 2 3 4 5 输出: 14 说明: 选择4作为聚集点，运费计算公式为1*2+2*2+3*1+5*1=14 选择5作为聚集点，运费计算公式为1*1+2*2+3*2+4*1=15

使用前缀和配合，枚举每个点为仓库，计算总费用，找出最小值，详见代码：