4. Zapeklitá situácia

Život banditu na divokom západe je náročná robota. Raz musí bandita vystrašiť ľudí v meste, inokedy sa zas pobiť v salóne. Je to makačka. Takýto život však má aj svoje výhody. Napríklad dnes sa banditom podaril mimoriadny úlovok – vykradli celý trezor banky Krvopotne Sporené Peniažky.

No keď utekali z mesta na chrbtoch svojich koní, začali sa im pred očami sypať zlaté mince a rodiť podlý plán hodný pravého banditu. Len čo vo svojom úkryte zosadli zo sedla, každý vytiahol svoj revolver a namierili ho na svojho najmenej obľúbeného kolegu. O jedného človeka menej v úkryte predsa znamená viac peňazí pre zvyšok!

Ako tam tak stáli, začali rozmýšľať. Ani jeden z nich nechce riskovať a vystreliť na niekoho iného, než na koho už má namierené. Tí lakomejší z nich začali dokonca špekulovať. “Ak zastrelím toho, na koho mám namierené až po tom, čo vystrelí on, tak mi zostane viac zlata!”

Koľko najmenej banditov môže prestrelku prežiť ak už má každý z nich vybraný svoj terč? Zistite poradie, v akom majú strieľať, aby sa každému preživšiemu ušlo čo najviac zlata.

Úloha

Dostanete zadanú situáciu – o každom banditovi viete, na koho mieri. O celej bande banditov viete nasledovné:

• Žiadni dvaja banditi nevystrelia naraz.

• Keď bandita vystrelí, tak jeho cieľ okamžite zomrie.

• Mŕtvy bandita už nestrieľa.

• Každý bandita vystrelí len na svoj pôvodný cieľ. Ak jeho cieľ už zabil niekto iný, tak bandita síce môže strieľať, no jeho strela nespraví nič.

Vašou úlohou je nájsť takú postupnosť strieľania, po ktorej zostane nažive najmenej banditov.

Formát vstupu

Na prvom riadku vstupu dostanete číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)) – počet banditov. Banditov očíslujeme celými číslami od \(1\) po \(n\), povedzme že od najškaredšieho.

Na ďalšom riadku dostanete postupnosť \(n\) celých čísel \(c_1\dots c_n\) (\(1\leq c_i\leq n\)). Platí, že bandita s číslom \(i\) mieri na banditu s číslom \(c_i\).

Môžete predpokladať, že žiadny bandita nemieri sám na seba.

Formát výstupu

Na prvý riadok vypíšte jedno číslo – počet banditov, ktorí zostanú nažive.

Na druhý riadok vypíšte číslo \(k\) – počet výstrelov, ktoré padli.

Na tretí riadok vypíšte \(k\) medzerou oddelených čísel – postupnosť banditov v poradí, v akom strieľali. (Vypisujte aj tých banditov, ktorí vystrelili a nikoho nezabili, ale nevypisujte banditov, ktorí zomreli skôr ako mohli vystreliť.)

Ak existuje viacero postupností, po ktorých zostane nažive najmenší počet banditov, vypíšte ľubovoľnú z nich.

Príklad

Input:

5
3 3 4 3 2

Output:

2
4
3 2 1 5

Všimnite si, že aj keď bandita 1 strieľal do mŕtveho banditu 3 zbytočne, tento výstrel sa mohol vyskytovať vo výsledku. Rovnako korektné riešenia sú napríklad aj “3 2 5” a “3 1 5”.