Hide

Problem C
Reiknirit

Languages en is

Sem lokaverkefni í áfanganum Þróun Hugbúnaðar ákvað Þórður að skrifa forrit sem þjónar miklum tilgangi. Forritið hans er útfærlsa á eftirfarandi sauðakóða:

  1. Les inn lista af tölum.

  2. Prenta listann.

  3. Fjarlægja öll eintök þess staks listans sem kemur oftast fyrir (ef margar tölur koma til greina er fjarlægt þá hæstu).

  4. Endurtaka $2$ og $3$ þar til listin er tómur.

Til dæmis, ef forritið fær lista $[1, 2, 1, 4, 4]$ prentar það $‘1\ 2\ 1\ 4\ 4’$, svo $‘1\ 2\ 1’$ og að lokum $‘2’$. Þegar Þórður sagði vini sínum Garðari frá þessu forriti benti Garðar honum á að í versta falli vex stærð úttkasins í öðru veldi með stærð inntaksins. Þetta hræddi Þórð, því hann vill geta sýnt niðurstöður úr stórum keyrlsum á forritinu sínu þegar kynnir verkefnið, en ef úttakið er of stórt kemst það ekki fyrir á glærurnar. Hann leitar því til þín til aðstoðar. Gefið lista af tölum, segðu Þórði hversu margar tölur verða í úttakinu.

Inntak

Fyrri lína inntaksins inniheldur heiltöluna $1 \leq n \leq 10^6$. Seinni lína inntaksins inniheldur $n$ heiltölur, $i$-ta slíka tala, $e_ i$, uppfyllir $1 \leq e_ i \leq 10^9$.

Úttak

Eina lína úttaksins skal innihalda fjölda talna sem forritið hans Þórðar prentar fyrir gefna listann.

Sample Input 1 Sample Output 1
5
1 2 1 4 4
9