Zadanie

Gregorova domáca úloha

Počet bodov: 30

Gregor mal dnes celkom zlý deň. Nielenže nepostúpil na krajské kolo Zenitu, ale ešte k tomu dnes na matematike zastupoval jeho najneobľúbenejší učiteľ. A veru aj dnes sa Gregorovi ušlo. Učiteľ napísal na tabuľu \(N\) čísel, a po dlhom dumavom pohľade na nich napokon s úškrnom zahlásil:

“Tak teda, deťúrence. Na domácu úlohu si dáme takéto neškodné cvičenie. Tu, hľa, som na tabuľu napísal veľa čísel a vy za úlohu musíte zistiť, ktoré čísla máme vynásobiť aby sme získali najväčší súčin. To by vás malo na dnes dobre zaneprázdniť.”

Ach. Kto by už len dokázal vymyslieť takú nudnú, zdĺhavú a nepraktickú domácu úlohu. Keby len bol niekto, kto by Gregorovi pomohol a vyriešil ju namiesto neho.

Vstup a Výstup

V prvom riadku je číslo \(N\): počet čísel. V druhom riadku je \(N\) čísel. Platí \(1 \leq N \leq 10^5\), žiadne z nich v absolútnej hodnote neprekročí \(10^9\).

Vyberte niektoré spomedzi týchto čísel tak, aby ich súčin bol čo najväčší. Odpoveď budeme reprezentovať pomocou reťazca dĺžky \(N\) pozostávajúceho z jednotiek a núl, kde nula bude označovať, že toľké číslo do súčinu neberieme a jednotka bude označovať, že ho berieme. Nakoniec si ešte popíšeme exaktné pravidlá, ako má tento reťazec vyzerať:

• Aspoň jeden znak bude jednotka, 1.
• Ak je na i-tej pozícii v reťazci 1, použijeme i-te číslo v našom súčine. Tento súčin musí byť maximálny možný.
• Spomedzi všetkých takýchto reťazcov má váš najmenej jednotiek
• Spomedzi všetkých takýchto reťazcov je váš lexikograficky najväčší. Keď lexikograficky porovnávame dva reťazce, pozrieme sa na najľavšiu pozíciu, na ktorej sa líšia. Lexikograficky väčší reťazec bude mať na tejto pozícii väčší znak (jednotku).¹

Navyše, v polovici vstupov je \(N \leq 20\) a maximálny súčin sa zmestí do 64-bitovej premennej so znamienkom.

Príklad

Input:

6
-2 -2 -3 4 5 1

Output:

101110

Najviac sa nám oplatí zobrať čísla \(-2, -3, 4, 5\). Jednotku neberieme, aby sme neporušili tretí bod a spomedzi dvoch \(-2\) si vyberieme tú ľavšiu, aby sme splnili aj štvrtý bod.