Background

一言

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

Description

土拨鼠 杯杯 想给$n$位阿根廷球迷们分$football$，他总共购买了$n$ 堆个数不相同 $football$。

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

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

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

Format

Input

一个整数$n$，表示$football$的堆数。

$n$个整数$a_i$，表示各堆$football$的个数。保证$n$堆$football$的个数总和为$n$的倍数。

Output

最少的移动次数。

Samples

5
6 1 3 2 3

3

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

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

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

Limitation

$1 \leq n \leq 10^6$

$1 \leq a_i \leq 10^9$