[old] Hari Poter

Harry Potter egy labirintusban van, amelyben a negyedik rész során (talán?) más varázslókkal versenyzett. A labirintus aktuális szakasza egy nagyon hosszú, dél–észak irányú folyosónak néz ki. Harry észak felé néz. Formálisan a folyosót tekinthetjük egy számegyenesnek, ahol Harry a 0 koordinátán áll, és a pozitív irány felé néz. Mindkét oldalról közelednek felé a főellenségei, a dementorok. Minden másodpercben Harry az alábbi három lépés egyikét hajthatja végre:

1. Varázslatot küld észak felé, amellyel eltávolítja az előtte lévő legközelebbi dementort.
2. Varázslatot küld dél felé, amellyel eltávolítja a mögötte lévő legközelebbi dementort.
3. Lép egy mezőt észak felé.

Vegyük észre, hogy Harry akkor is dobhat varázslatot valamelyik irányba, ha abban az irányban nincs dementor. Miután Harry végrehajtja a lépését, az összes megmaradt dementor egy mezővel közelebb lép hozzá. Amikor a dementorok utolérik Harryt, többé nem tud mozogni és varázsolni. Harry nem hajthat végre két azonos típusú lépést egymás után. Továbbá, Harry legfeljebb 10^6 lépést hajthat végre, mielőtt túlságosan elfárad.

Azt kell kiíratni, hogy legfeljebb hány dementort tud Harry kiiktatni, mielőtt utolérik vagy túlságosan elfárad. Ezen felül írjátok ki a lépések sorozatát is, amelyet Harrynek végre kell hajtania ahhoz, hogy ezt elérje. Ha több lehetséges sorozat is van, bármelyik kiírható.

A bemenet leírása

A szabványos bemenet első sorában egy N egész szám szerepel, amely a dementorok számát jelöli.

A szabványos bemenet második sorában N egész szám található. Az i-edik közülük x_i, és az i-edik dementor pozícióját jelöli.

A kimenet leírása

Az első sorban a d számot kell kiírni, amely a Harry által kiiktatható dementorok maximális számát jelöli. A második sorban egy s karaktersorozatot kell megjeleníteni. A sorozat minden karaktere 1, 2 vagy 3 kell, hogy legyen. Az i-edik karakter, s_i, azt a lépést jelenti, amelyet Harrynek az i-edik lépésben kell végrehajtania.

1. példa

Bemenet

2
-5 5

Kimenet

2
2321

A példa magyarázata

Az első példában két dementor van. Az egyik a -5 pozíción, a másik az 5 pozíción található. Harry az első lépésben dél felé varázsol, és ezzel kiiktatja a -5 pozíción lévő dementort. Ezt követően az 5 pozíción lévő dementor egy mezővel közelebb lép, és a 4 pozícióra kerül. A második lépésben Harry egy mezőt észak felé lép, így az 1 pozícióra kerül. Harry lépése után az előtte lévő dementor közelebb lép, a 4 pozícióról a 3 pozícióra. A harmadik lépésben Harry dél felé varázsol. Mivel nincs mögötte dementor, a varázslat senkit sem iktat ki. A harmadik lépés után a 3 pozíción lévő dementor a 2 pozícióra lép. A negyedik lépésben Harry észak felé varázsol, és kiiktatja a második dementort is. Tehát lehetséges mindkét dementor kiiktatása. Vegyük észre, hogy a 12 is érvényes lépéssorozat lett volna, amellyel szintén mindkét dementor kiiktatható.

2. példa

Bemenet

2
-1 1

Kimenet

1
1

A példa magyarázata

A második példában ismét két dementor van. Az egyik a -1, a másik az 1 pozíción. Vegyük észre, hogy Harry legfeljebb egy dementort tud kiiktatni egy lépés alatt. Mivel mindkét dementor közvetlenül mellette van, az első lépést követően az egyik biztosan utoléri. Harry az első lépésben észak felé varázsol, és ezzel kiiktatja az 1 pozíción lévő dementort. Ezután a -1 pozíción lévő dementor egy mezővel közelebb lép, és a 0 pozícióra kerül. Ekkor a dementor utoléri Harryt, és többé nem tud semmilyen lépést sem végrehajtani. Tehát a maximálisan kiiktatható dementorok száma 1.

Korlátozások

• 1 \leq n \leq 200.000.
• |x_i| \leq 10^9 és x_i \neq 0; 1 \leq i \leq n-re.
• x_i \neq x_j; i \neq j-re.
• Az x sorozat nem feltétlenül rendezett.
• A kiírt lépések teljes száma legfeljebb 10^6 lehet.

A tesztpéldák öt diszjunkt csoportba vannak sorolva:

• A 10 pontot érő tesztpéldákban: érvényes, hogy n \leq 10
• A 15 pontot érő tesztpéldákban: érvényes, hogy x_i < 0; 1 \leq i \leq n-re.
• A 20 pontot érő tesztpéldákban: érvényes, hogy x_i > 0; 1 \leq i \leq n-re.
• A 15 pontot érő tesztpéldákban: érvényes, hogy |x_i| páros, 1 \leq i \leq n.
• A 40 pontot érő tesztpéldákban: nincsenek további korlátozások.

Ha az adott példában helyesen írjátok ki a maximális dementorszámot (d-t), de nem adjátok meg a rekonstrukciót (vagyis a lépéssorozatot), akkor az adott példára a pontszámok 40\%át kapjátok meg.

Megjegyzés

Ha 10^6-nál több lépést írtok ki, akkor legfeljebb a pontok 40\%-át kaphatjátok meg az adott példára (feltéve, hogy a dementorok száma helyes). Hasonlóképpen, ha tovább írjátok a lépéseket azután is, hogy a dementorok utolérték Harryt, legfeljebb a pontok 40\%-át kaphatjátok meg az adott példára.