Hari Poter

Хари Потер ше находзи у лавиринту у хторим ше под час штвартей часци обеговал зоз другима чаривнїками. У тей хвильки часц лавиринту у хторей ше находзи випатра як єден барз длугоки конк ориєнтовани од югу ґу сиверу. Хари обрацени ґу сиверу. Формално, конк можеме задумац як числову просту, а Хари ше находзи на координати 0 и обрацени є ґу позитивним числом. З обидвох бокох му приходза його архинєприятелє, дементоре. Каждей секунди Хари може направиц єден з шлїдуюцих трох рухох:

1. Може руциц чародїйство на сивер, з чим знїщи дементора хтори му найблїжей и хтори ше находзи опрез нього. • Може руцуц чародїйство на юг, та знїщи дементора хтори ше находзи найблїжей за нїм.
2. Може ше помкнуц єдно польо ґу сиверу.

Треба най знаце же Хари може руцац чародїйства у даяким смислу аж и кед там нєт анї єден дементор. Кед Хари окончи свой рух, шицки други дементори хтори остали приблїжа му ше за єдно польо. Кед дементори сцигню по Хария, вон ше вецей нє може рушац анї руцац чародїйства. Хари нє шме направиц два исти рухи за шором. Попри того, Хари може направиц найвецей 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\% боди за тот приклад.