[ol2] Hari Poter

Хари Потер се налази у лавиринту у којем се током четвртог дела (ваљда?) тркао са другим чаробњацима. Тренутна деоница лавиринта изгледа као један веома дугачак ходник оријентисан од југа ка северу. Хари је окренут ка северу. Формално, ходник можемо да замислимо као бројевну праву, са Харијем на координати 0 и окренутим ка позитивним бројевима. Са обе стране му прилазе његови архинепријатељи, дементори. Сваке секунде Хари може да направи један од следећа три потеза:

1. Баци чин ка северу, чиме уклони најближег дементора испред себе.
2. Баци чин ка југу, чиме уклони најближег дементора иза себе.
3. Помери се за једно поље ка северу.

Приметите да Хари може да баци чин у неком смеру чак и када не постоји дементор у том смеру. Након што Хари изведе свој потез, сви дементори који преостану му се приближе за једно поље. Када дементори сустигну Харија, он више не може да се креће и баца чини. Хари не сме да направи два потеза истог типа за редом јер иначе задатак не би био довољно тежак. Поред тога, Хари може да изврши највише 10^6 потеза пре него што се превише умори.

Исписати колико највише дементора Хари може да елиминише, пре него што га сустигну или се превише умори. Додатно, исписати и редослед потеза које Хари треба да изврши да би то постигао. Уколико има више могућих редоследа, исписати било који.

Опис улаза

У првој линији стандардног улаза дат је цео број N, број дементора.

У другој линији стандардног улаза, дато је N целих бројева. i-ти од њих је x_i и представља позицију i-тог дементора.

Опис излаза

У првој линији исписати максималан број дементора d које Хари може да елиминише. У другој линији исписати ниску карактера s. Сви карактери ове ниске морају бити 1, 2 или 3. i-ти карактер, s_i, представља потез коју Хари треба да направи у i-том кораку.

Пример 1

Улаз

2
-5 5

Излаз

2
2321

Објашњење примера 1

У првом примеру постоје два дементора. Један се налази на позицији -5, други се налази на позицији 5. Хари ће у првом потезу бацити чин ка југу и тиме елиминисати дементора на позицији -5. Након тога ће му се дементор са позиције 5 приближити за једно поље и померити се на позицију 4. У другом потезу, Хари ће се померити за једно поље ка северу и наћи се на позицији 1. Након Харијевог потеза, дементор испред њега ће му се приближити и померити са позиције 4 на позицију 3. У трећем потезу, Хари ће бацити чин ка југу. Пошто се иза њега не налази ниједан дементор, чин неће никога елиминисати. Након трећег потеза, дементор са позиције 3 ће се померити на позицију 2. У четвртом потезу, Хари ће бацити чин ка северу и елиминисати и другог дементора. Према томе, могуће је елиминисати оба дементора. Приметите и да је 12 такође био валидан редослед операција, којим се елиминишу оба дементора.

Пример 2

Улаз

2
-1 1

Излаз

1
1

Објашњење примера 2

У другом примеру поново постоје два дементора. Један се налази на позицији -1, други се налази на позицији 1. Приметимо да Хари може да елиминише највише једног дементора по потезу. Пошто су му оба дементора суседна, након првог потеза, један од та два дементора ће га сустићи. Хари ће у првом потезу бацити чин ка северу и тиме елиминисати дементора на позицији 1. Након тога ће му се дементор са позиције -1 приближити за једно поље и померити се на позицију 0. У том тренутку, дементори су га сустигли и Хари више не може да повлачи потезе. Према томе, максималан број дементора које је могуће елиминисати је 1.

Ограничења и бодовање

• 1 \leq n \leq 200.000.
• |x_i| \leq 10^9 и x_i \neq 0, за 1 \leq i \leq n.
• x_i \neq x_j за i \neq j.
• Низ x не мора бити сортиран.
• Укупан број исписаних потеза може да буде највише 10^6.

Тест примери су подељени у 5 дисјунктних група:

• У тестовима вредним 10 поена: важи n \leq 10
• У тестовима вредним 15 поена: важи x_i < 0, за 1 \leq i \leq n.
• У тестовима вредним 20 поена: важи x_i > 0, за 1 \leq i \leq n.
• У тестовима вредним 15 поена: важи |x_i| је парно, 1 \leq i \leq n.
• У тестовима вредним 40 поена: без додатних ограничења.

Уколико у датом примеру тачно испишете максималан број дементора d, али не и реконструкцију, добијате 40\% бодова за тај пример.

Напомена

Уколико испишете преко 10^6 потеза, добијате највише 40\% бодова за тај пример (уколико је број дементора тачан). Слично, уколико наставите да исписујете потезе након што дементори сустигну Харија, добијате највише 40\% бодова за тај пример.