[ol2] Hari Poter

Harry Potter nalazi se u labirintu u kojem se tijekom četvrtoga dijela (valjda?) utrkivao s drugim čarobnjacima. Trenutačna dionica labirinta izgleda kao jedan vrlo dugačak hodnik orijentiran od juga k sjeveru. Harry je okrenut k sjeveru. Formalno, hodnik možemo zamisliti kao brojevni pravac, s Harryjem na koordinati 0 i okrenutim k pozitivnim brojevima. S obje strane mu prilaze njegovi arhineprijatelji, dementori. Svake sekunde Harry može napraviti jedan od sljedeća tri poteza:

1. Baciti čini k sjeveru, čime ukloni najbližeg dementora ispred sebe.
2. Baciti čini k jugu, čime ukloni najbližeg dementora iza sebe.
3. Pomjeriti se za jedno polje k sjeveru.

Primijetite kako Harry može baciti čini u nekom smjeru čak i kada ne postoji dementor u tom smjeru. Nakon što Harry izvede svoj potez, svi dementori koji preostanu mu se približe za jedno polje. Kada dementori sustignu Harryja, on se više ne može kretati i bacati čini. Harry ne smije napraviti dva poteza istog tipa za redom jer inače zadatak ne bi bio dovoljno težak. Pored toga, Harry može izvršiti najviše 10^6 poteza prije nego što se previše umori.

Ispisati koliko najviše dementora Harry može eliminirati, prije nego što ga sustignu ili se previše umori. Dodatno, ispisati i redoslijed poteza koje Harry treba izvršiti kako bi to postigao. Ako ima više mogućih redoslijeda, ispisati bilo koji.

Opis ulaza

U prvoj liniji standardnog ulaza dan je cijeli broj N, broj dementora.

U drugoj liniji standardnog ulaza, dano je N cijelih brojeva. i-ti od njih je x_i i predstavlja poziciju i-tog dementora.

Opis izlaza

U prvoj liniji ispisati maksimalan broj dementora d koje Harry može eliminirati. U drugoj liniji ispisati nisku karaktera s. Svi karakteri ove niske moraju biti 1, 2 ili 3. i-ti karakter, s_i, predstavlja potez koju Harry treba napraviti u i-tom koraku.

Primjer 1

Ulaz

2
-5 5

Izlaz

2
2321

Objašnjenje primjera 1

U prvome primjeru postoje dva dementora. Jedan se nalazi na poziciji -5, drugi se nalazi na poziciji 5. Harry će u prvom potezu baciti čini k jugu i time eliminirati dementora na poziciji -5. Nakon toga će mu se dementor s pozicije 5 пpribližiti za jedno polje i pomjeriti se na poziciju 4. U drugome potezu, Harry će se pomjeriti za jedno polje k sjeveru i naći se na poziciji 1. Nakon Harryjevog poteza, dementor ispred njega će mu se približiti i pomjeriti s pozicije 4 na poziciju 3. U trećemu potezu, Harry će baciti čini k jugu. Budući da se iza njega ne nalazi nijedan dementor, čini neće nikoga eliminirati. Nakon trećega poteza, dementor s pozicije 3 će se pomjeriti na poziciju 2. U četvrtome potezu, Harry će baciti čini k sjeveru i eliminirati i drugog dementora. Prema tome, moguće je eliminirati oba dementora. Primijetite i kako je 12 također bio validan redoslijed operacija, kojim se eliminiraju oba dementora.

Primjer 2

Ulaz

2
-1 1

Izlaz

1
1

Objašnjenje primjera 2

U drugome primjeru ponovo postoje dva dementora. Jedan se nalazi na poziciji -1, drugi se nalazi na poziciji 1. Primijetimo kako Harry može eliminirati najviše jednog dementora po potezu. Budući da su mu oba dementora susjedna, nakon prvog poteza, jedan od ta dva dementora će ga sustići. Harry će u prvom potezu baciti čini k sjeveru i time eliminirati dementora na poziciji 1. Nakon toga će mu se dementor s pozicije -1 približiti za jedno polje i pomjeriti se na poziciju 0. U tome trenutku, dementori su ga sustigli i Hari više ne može povlačiti poteze. Prema tome, maksimalan broj dementora koje je moguće eliminirati je 1.

Ograničenja i bodovanje

• 1 \leq n \leq 200.000.
• |x_i| \leq 10^9 i x_i \neq 0, za 1 \leq i \leq n.
• x_i \neq x_j za i \neq j.
• Niska x ne mora biti sortirana.
• Ukupan broj ispisanih poteza može biti najviše 10^6.

Test primjeri su podijeljeni u 5 disjunktnih skupina:

• U testovima vrijednim 10 bodova: važi n \leq 10
• U testovima vrijednim 15 bodova: važi x_i < 0, za 1 \leq i \leq n.
• U testovima vrijednim 20 bodova: važi x_i > 0, za 1 \leq i \leq n.
• U testovima vrijednim 15 bodova: važi |x_i| je parno, 1 \leq i \leq n.
• U testovima vrijednim 40 bodova: bez dodatnih ograničenja.

Ako u danom primjeru točno ispišete najveći broj dementora d, ali ne i rekonstrukciju, dobivate 40\% bodova za taj primjer.

Napomena

Ako ispišete preko 10^6 poteza, dobivate najviše 40\% bodova za taj primjer (ako je broj dementora točan). Slično, ako nastavite ispisivati poteze nakon što dementori sustignu Harryja, dobivate najviše 40\% bodova za taj primjer.