Као што је већини ђака познато, драга професорка роботике Катарина много воли да се игра лего роботима и коцкицама. Овај пут на час je донела специјалног робота и \(n\) кула коцкица. На свакој кули се налази одређен број наслаганих коцкица које представљају висину те куле, тачније \(i\)-та кула има висину \(A_i\) (састављена је од тачно \(A_i\) коцкица). Ђаци су приметили да не садрже све куле подједнак број коцкица и желе то да промене помоћу професоркиног специјалног робота. Наиме, овај робот може извршити следећу операцију:

• Робот може да узме две или три коцкице са бесконачне гомиле која се налази поред датих кула (Катарина толико воли коцкице да их има у неограниченим количинама) и да те коцкице стави на једну од \(n\) кула. Тако се у једној операцији повећава висина одређене куле за \(2\) или \(3\) коцкице.

Како су ђаци и сама професрока мало нестрпљиви, молимо вас помозите им да што пре израчунају минималан број операција потребних роботу да изједначи висине свих \(n\) кула.

Опис улаза

У првом реду стандардног улаза налази се природан број \(n\), број кула које је донела професорка. У другом реду налази се низ \(А\) од \(n\) природних бројева раздвојених размаком, где \(A_i\) представља висину \(i\)-те куле.

Опис излаза

У првом и једином реду стандардног излаза исписати цео број који представља минималан број операција наведених у тексту задатка потребних роботу да изједначи висине свих кула.

Примери

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            3<br/>                                          
            7 10 5
        </span>
        <span class="exampleoutput">
            3
        </span>
    </div>
</div>

<div class="panel panel-default">
    <div class="panel-heading">
        <span class="pull-left" style="width: 48%;">Ulaz</span>
        <span style="padding-left: 15px;">Izlaz</span>
    </div>
    <div class="panel-body">
        <span class="pull-left exampleinput">
            5<br/>
            1 5 1 5 2
        </span>
        <span class="exampleoutput">
            5
        </span>
    </div>
</div>

Објашњење примера

У првом примеру укупно имамо \(3\) куле са коцкицама. Прва кула је висине \(7\), друга кула је висине \(10\), док је трећа кула висине \(5\). Робот може изједначити висине кула у \(3\) операције :

1. Робот додаје \(3\) коцкице на прву кулу. Сада су висине кула { \(10\), \(10\), \(5\)}.
2. Робот додаје \(3\) коцкице на трећу кулу. Тренутне висине кула су { \(10\), \(10\), \(8\)}.
3. Робот додаје \(2\) коцкице на трећу кулу. Коначне висине кула су { \(10\), \(10\), \(10\)}.

Показали смо како робот може да изједначи висине кула у \(3\) операције, може се показати да је немогуће изједначити поменуте куле у мање потеза. Минималан број потребних операција је \(3\).

Ограничења

Тест примери су подељени у две дисјунктне гурпе: * У тест примерима који вреде \(40\) поена важиће \(1 \leq n \leq 100\) и \(1 \leq A_i \leq 1000\). * У тест примерима који вреде \(60\) поена важиће \(1 \leq n \leq 10^5\) и \(1 \leq A_i \leq 10^9\).