题目描述

保山市的 $n$ 个特产商店呈环形排列在古城周围，每个商店有 $a_i$ 件永子围棋纪念品。商店之间只能向左右相邻商店调配货物。每调配一件纪念品的物流成本为 $1$。

输入格式

第一行：商店个数 $n$

接下来 $n$ 行：每行一个整数 $a_i$，表示每个商店的纪念品库存量

输出格式

输出使所有商店纪念品数量相等的最小物流成本。

4
1
2
5
4

4

样例解释

平均每个商店应有 $(1+2+5+4)/4 = 3$ 件纪念品。 最优调配方案（总成本=4）：

• 商店3给商店2 两件（成本2）
• 商店4给商店1 一件（成本1）
• 商店2给商店1 一件（成本1）

5
5
2
3
6
4

4

样例解释

平均每个商店应有 $(5+2+3+6+4)/5 = 4$ 件纪念品。 最优调配方案（总成本=4）：

• 商店1给商店2 一件（成本1）
• 商店4给商店3 两件（成本2）
• 商店3给商店2 一件（成本1）

数据范围

对于所有测试数据，保证 $\sum a_i$ 是 $n$ 的倍数,$1 \leq n \leq 10^6$,$1 \leq a_i \leq 1.5 \times 10^9$