Pyöreän pöydän ritarit asettuivat syömään, mutta tarjoilija oli jakanut haarukat huolimattomasti. Haarukoiden kokonaismäärä pöydässä on kuitenkin oikea, eli jokaiselle ritarille on yksi haarukka.

Tehtäväsi on etsiä optimaalinen tapa, miten ritarit saavat jaettua haarukat. Mikä on pienin siirtojen määrä, kun yhdellä siirrolla ritari voi antaa itsellään olevan haarukan jommallekummalle vieressä istuvalle?

Syöte

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

Seuraavalla rivillä on n kokonaislukua r_1,r_2,\ldots,r_n: montako haarukkaa ritarilla r_k on alussa.

Tuloste

Ohjelman tulee tulostaa yksi kokonaisluku: pienin mahdollinen siirtojen määrä, joiden jälkeen jokaisella ritarilla on yksi haarukka.

Rajat

• 1 \le n \le 10^5
• 0 \leq r_k \leq n
• r_1+r_2+\cdots+r_n=n

Esimerkki

Syöte:

5
3 1 0 1 0

Tuloste:

3

Yksi ratkaisu on, että ritari 1 antaa ensin haarukat ritari 2:lle ja ritari 5:lle (2 siirtoa). Tämän jälkeen ritari 2 antaa haarukan ritari 3:lle (1 siirto).