Partitie

Un șir $x_1, x_2, \dots x_k$ se numește mic dacă pentru fiecare $i$ de la $1$ la $k$ avem $x_i \leq i$.

Cerință

Se dă $N$ și un șir mic $a_1, a_2, \dots a_N$ de numere naturale nenule. Fiecărui element de la $1$ la $N$ să i se ascoieze un număr, $1$ sau $2$ astfel încât suma valorilor de pe pozițiile cu $1$ este egală cu suma valorilor de pe pozițiile cu $2$. Dacă nu se poate, se va afișa $-1$.

Mai exact, să se partiționeze șirul în două mulțimi de sumă egală.

Date de intrare

Pe prima linie a fișierului de intrare partitie.in se află numărul natural $N$. Pe a doua linie se află șirul $a_1, a_2, \dots a_N$.

Date de ieșire

Pe prima linie a fișierului de ieșire partitie.out se va afișa $-1$ dacă nu există nicio partiție. Dacă există se va afișa un șir de lungime $N$. Al $i$-lea caracter este $1$ dacă elementul $i$ face parte din prima mulțime sau $2$ dacă face parte din a doua.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq a_i \leq i$ pentru fiecare $i$ de la $1$ la $N$.
• Pentru teste în valoare de $31$ de puncte, $N \leq 4$

Exemplul 1

partitie.in

6
1 1 2 4 3 5

partitie.out

211221

Explicație

Suma valorilor de pe pozițiile cu $1$ este $1 + 2 + 5 = 8$, iar suma valorilor de pe pozițiile cu $2$ este $1 + 4 + 3 = 8$. Observăm că aceste sume sunt egale.

Exemplul 2

partitie.in

4
1 2 3 3

partitie.out

-1

Explicație

Se observă că nu există nicio partiție în două mulțimi de sumă egală.