题目描述

给定一个长度为 $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$。

样例数据

输入:

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