#P274. 土拨鼠分足球

土拨鼠分足球

Background

一言

我今天的苦,何尝不是你来日的难。

Description

土拨鼠 杯杯 想给nn位阿根廷球迷们分footballfootball,他总共购买了nn 个数不相同 footballfootball

为了防止阿根廷球迷们不再支持梅西,土拨鼠 杯杯 想要把这nnfootballfootball分成同样多的。

土拨鼠 杯杯 每次只能把一堆footballfootball中的一些footballfootball移动到相邻的一堆中,他一次可以拿多个或一个。

而且为了不耽误看球赛,他想移动尽可能少的次数。请你告诉 杯杯 最少需要移动几次。

Format

Input

一个整数nn,表示footballfootball的堆数。

nn个整数aia_i,表示各堆footballfootball的个数。保证nnfootballfootball的个数总和为nn的倍数。

Output

最少的移动次数。

Samples

5
6 1 3 2 3
3

第一次移动:1 --3个--> 2

第二次移动:3 --1个--> 4

第三次移动:2 --1个--> 3

Limitation

1n1061 \leq n \leq 10^6

1ai1091 \leq a_i \leq 10^9