Balboa s-a indragostit nebuneste de noua fata din oras. Din pacate, el nu stie daca sentimentul este reciproc. Ca urmare, acesta a cumparat $N$ trandafiri, trandafirul $i$ avand $V{~i~}$ petale. Acuma Balboa doreste sa joace "Ma iubeste, nu ma iubeste!" varianta originala. La un pas el are $2$ variante:
* Rupe o petala dintr-un trandafir

* Selecteaza $2$ submultimi identice de trandafiri si arunca unul din seturi la gunoi (nu vrea sa aiba parte de un deja-vu).

* Selecteaza $2$ seturi identice de trandafiri si arunca unul din seturi la gunoi (nu vrea sa aibe dupa un deja-vu)

Balboa va aplica una din cele $2$ operatii pana cand va ramane cu un singur trandafir (care poate sa aibe oricate petale). Deoarece este o persoana foarte grabita, va roaga sa ii spuneti numarul minim de operatii pe care trebuie sa le efectueze pentru a finaliza jocul.

h2. Restricţii
* $1 ≤ N ≤ 100.000$

* $1 ≤ V{~i~} ≤ 2^31^ - 1$
* Toti trandafirii au initial numar diferit de petale

* $1 ≤ V{~i~} ≤ 1.000.000.000$

h2. Exemplu