[ol2] Hari Poter

Harry Potter – dementori

Harry Potter sa nachádza v bludisku, v ktorom počas štvrtého dielu súťažil s inými čarodejníkmi. Aktuálny úsek bludiska je dlhá chodba orientovaná z juhu na sever. Chodbu môžeme modelovať ako číselnú os, Harry stojí na pozícii 0 a je otočený k severu.

Z oboch strán sa k nemu približujú dementori. Každú sekundu môže Harry vykonať jeden z troch ťahov:

1. zoslať kúzlo na sever – odstráni najbližšieho dementora pred sebou,
2. zoslať kúzlo na juh – odstráni najbližšieho dementora za sebou,
3. posunúť sa o jedno pole na sever.

Kúzlo môže zoslať aj v smere, kde žiadny dementor nie je. Po Harryho ťahu sa všetci zostávajúci dementori posunú o jedno pole bližšie. Keď dementori Harryho dostihnú, už nemôže robiť ďalšie ťahy. Harry nesmie vykonať dva rovnaké typy ťahu po sebe a môže vykonať najviac 10^6 ťahov.

Treba vypísať maximálny počet dementorov, ktorých vie Harry odstrániť, a tiež postupnosť ťahov (znaky 1, 2, 3). Ak existuje viac riešení, stačí ľubovoľné.

Vstup: Prvý riadok obsahuje celé číslo N – počet dementorov. Druhý riadok obsahuje N celých čísel – ich pozície.

Výstup: Na prvý riadok vypíšte maximálny počet odstránených dementorov. Na druhý riadok vypíšte postupnosť ťahov.

Obmedzenia: 1 ≤ N ≤ 200 000 |xi| ≤ 10^9, xi ≠ 0, všetky xi sú rôzne.