负载平衡问题

题目描述

$G$ 公司有 $n$ 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。

输入输出格式

输入格式


文件的第 $1$ 行中有 $1$ 个正整数 $n$,表示有 $n$ 个仓库。 第 $2$ 行中有 $n$ 个正整数,表示 $n$ 个仓库的库存量。

输出格式


输出最少搬运量。

输入输出样例

输入样例 #1

5
17 9 14 16 4

输出样例 #1

11

说明

$1 \leq n \leq 100$