Description

There are n piles of cards, numbered 1, 2, ..., n. Each pile has a certain number of cards, but the total number of cards must be a multiple of n. You can take any number of cards from a pile and move them.

The rules for moving cards are as follows:

• Cards taken from pile 1 can only be moved to pile 2.
• Cards taken from pile n can only be moved to pile n−1.
• Cards taken from any other pile can be moved to either the adjacent left or right pile.

The goal is to find a method of moving cards with the least number of moves so that each pile has the same number of cards.

For example, when n=4, the four piles have the following number of cards:
① 9　② 8　③ 17　④ 6

It takes 3 moves to achieve the goal:

1. Move 4 cards from ③ to ④ (resulting in 9, 8, 13, 10).
2. Move 3 cards from ③ to ② (resulting in 9, 11, 10, 10).
3. Move 1 card from ② to ① (resulting in 10, 10, 10, 10).

Input Format

n (number of piles, 1 ≤ n ≤ 100)
a1 a2 … an (initial number of cards in each pile, 1 ≤ ai ≤ 10000).

Output Format

The minimum number of moves required for all piles to have an equal number of cards.

4
9 8 17 6

3