4. Zajtra dávam výpoveď!

Myslíte si, že programovanie v skutočnej softvérovej firme bude jednoduché? Syseľ si to myslel tiež. Postupne si však uvedomuje, ako veľmi sa mýlil.

Syseľ je zamestnaný vo firme Kontra Systémové Programy a na vlastnej koži zažíva, čo je to život programátora z povolania. Každé ráno sa mu vo dverách objaví šéf a hromovým hlasom zvolá všetky nové požiadavky, ktoré by mal Syseľ splniť.

Jedno ráno príde a zahuláka: “Nech sú tie tlačidlá oblejšie! Nech to načítavanie trvá trochu dlhšie, veď to vyzerá, ako keby ten program nič nerobil! Prečo to vôbec nepadá?”. A zvyšok dňa Syseľ tvrdo maká, aby vyhovel šéfovým požiadavkám. Na druhý deň šéf rozcapí dvere a zručí: “Prečo sú tie tlačidlá také oblé? To načítavanie aj niekedy skončí? V tom programe sa nedá robiť! Každú chvíľu padá!”. A zvyšok dňa Syseľ znova tvrdo maká, aby vyhovel novým šéfovým požiadavkám. Najhoršie je, že Syseľ nemôže prepisovať kód, ktorý už je napísaný. To by potom budilo dojem, že šéfove požiadavky neboli konzistentné. Môže len na koniec dopisovať ďalšie a ďalšie riadky. Celý kód potom vyzerá ako veľká guľa bahna, má tisíce riadkov, ale šéf je spokojný!

Sysľov kolega Roman na tom nie je o nič lepšie. Roman určuje, akým číslom bude označená nová verzia Sysľovej aplikácie. Podobne ako sa predlžuje Sysľov program, toto číslo sa musí každý deň predĺžiť o jednu cifru, pričom jeho začiatok sa už nesmie meniť. Naviac, každé ráno si šéf zmyslí, čím má byť toto číslo deliteľné.

V minulosti šéf postupne vyberal čísla 1, 2, 3, 4, … avšak pri verzii 3608528850368400786036725 sa nedalo pokračovať ďalej¹ a šéf musel zastaviť vývoj aplikácie.

Pri novej aplikácii si šéf dáva väčší pozor a vyberá len čísla z rozsahu 1 až 10 a čísla nevyberá postupne zaradom, ale náhodne. No a Roman musí celé dni počítať správnu verziu programu. Vedeli by ste mu s tým pomôcť?

Úloha

Dostanete postupnosť \(n\) celých čísel v rozsahu \(1\) až \(10\) – zoznam šéfových požiadaviek pre jednotlivé dni. Vypočítajte číslo, o ktorom pre všetky \(i\) od \(1\) po \(n\) platí, že číslo, ktoré vznikne spojením prvých \(i\) cifier tohto čísla je deliteľné \(i\)-tou šéfovou požiadavkou.

Ak je možností viacero, nájdite najmenšie z vyhovujúcich čísel.

Formát vstupu

Na prvom riadku sa nachádza číslo \(2 \leq n \leq 200\,000\) – počet šéfových požiadaviek. Na druhom riadku sa nachádza \(n\) medzerami oddelených čísel \(p_i\) – šéfove požiadavky. Platí, že \(1 \leq p_i \leq 10\). Čiastočné body samozrejme dostanete, aj keď vyriešite úlohu pre malé \(n\leq 9\), \(n\leq 18\), \(n\leq 100\), \(n\leq 10\,000\) alebo \(n\leq 100\,000\).

Formát výstupu

Vypíšte jeden riadok, a na ňom jediné číslo – najmenšie \(n\)-ciferné číslo \(c\) také, že ak zoberieme prvých \(i\) cifier z čísla \(c\), tak takéto číslo bude deliteľné požiadavkou \(p_i\).

Mimochodom, \(n\)-ciferné číslo pre \(n \geq 2\) nemôže mať prvú cifru nulu.

Príklad

Input:

10
1 2 3 4 5 6 7 8 9 10

Output:

1020005640

Odpoveď, bohužiaľ, nemôže byť prvých 10 cifier Romanovho skvelého čísla (3608528850), pretože to nie je najmenšie možné číslo vyhovujúce požiadavkám.

Input:

7
3 9 7 5 6 7 4

Output:

3640212

Input:

13
9 4 7 8 2 3 7 4 9 7 2 3 4

Output:

9240000035012