圆环选址(Circular Location)

题目描述

给定长度为 $n$ 的环状数列 $a_1,\ldots,a_n$（$a_1$ 与 $a_n$ 相邻），每处有一堆物资。选一个位置将所有物资聚集，物资沿相邻位置搬运，每单位物资移动一单位距离需一单位运费。求最小总运费。

输入格式

• 第一行：整数 $n$
• 第二行：$n$ 个整数 $a_1,\ldots,a_n$

输出格式

• 单个整数：最小总运费。

样例输入 #1

5
1 2 3 4 5

样例输出 #1

14

说明：选位置4（值为4）为聚集点，$1\times2+2\times2+3\times1+5\times1=14$

数据范围

• 对于 $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$

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐。

测试点分布