Pyöreän pöydän ympärillä istuu n lasta. Tiedät jokaisesta lapsesta, kuinka monta karkkia hänellä on.

Tehtäväsi on jakaa karkit tasan lasten kesken. Saat valita joka siirrolla yhden lapsen, joka antaa yhden karkin vasemmalla tai oikealla istuvalle naapurille.

Mikä on pienin määrä siirtoja, jolla karkit saadaan tasattua?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: lasten määrä.

Seuraavalla rivillä on n kokonaislukua k_1,k_2,\ldots,k_n: kunkin lapsen karkkien määrä alussa.

Karkkien yhteismäärä on jaollinen lasten määrällä.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako siirtoa tarvitaan.

Rajat

• 1 \le n \le 10^5
• 1 \le k_i \le 10^9

Esimerkki

Syöte:

4
2 5 3 6

Tuloste:

3