Trandafiri

trandafiri

== include(page="template/taskheader" task_id="trandafiri") ==

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).
 
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.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $trandafiri.in$ va contine pe prima linie un numar natural $N$, reprezentand numarul de trandafiri. Pe urmatoarea linie vor fi $N$ numere, reprezentand numarul de petale ale fiecarui trandafir.

Fişierul de intrare $trandafiri.in$ ...

h2. Date de ieşire

Fişierul de ieşire $trandafiri.out$ va contine un singur numar natural reprezentand numarul minim de operatii necesare pentru a finaliza jocul.

În fişierul de ieşire $trandafiri.out$ ...

h2. Restricţii

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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. trandafiri.in |_. trandafiri.out |

|3
1 3 5
|6

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="trandafiri") ==