409281: GYM103476 B Julia and Flower Beds

Julia is about to move into her new house! There are two flower beds in the garden at the new place, currently containing no flowers. The closest flower shop "Innoflower" sells $$$n$$$ types of flowers selling, enumerated from $$$1$$$ to $$$n$$$.

Julia has already bought all flowers she plans to plant: she bought exactly $$$a_i$$$ flowers of type $$$i$$$. In addition, to make sure the design is diverse, Julia has made an additional restriction: the number of flowers of type $$$i$$$ does not exceed $$$i$$$ (in other words, $$$1 \le a_i \le i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$).

Julia wants to plant all flowers in her two flower beds in the most beautiful way possible. To keep the harmony, she plans to put all flowers of the same type in one flower bed (that is, all flowers of type $$$i$$$ must be either in the first flower bed or in the second one). At the same time, to ensure maximum symmetry, Julia wants the difference in the number of flowers in flower beds to be as small as possible.

Housewarming party is too soon, so help Julia out and find the required planting of flowers!

First line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of different types of flowers in "Innoflower".

In the second line, there are $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le i$$$) — the number of flowers of each type.

In the first line, print one non-negative integer — the least possible difference of numbers of flowers in flower beds.

In the second line, print the planting of flowers in the following format: $$$n$$$ integers $$$w_1, \ldots, w_n$$$, where $$$w_i = 1$$$ if all flowers of type $$$i$$$ should be planted in the first flower bed, and $$$w_i = 2$$$ otherwise.

If there are more than one possible plantings with the minimum difference, print any of them.

5
1 2 1 4 3

1
1 2 1 1 2

2
1 1

0
2 1

In the first example, we have $$$1+1+4=6$$$ flowers in the first flower bed and $$$2+3=5$$$ flowers in the second, so the difference equals $$$1$$$. It is impossible to plant the same number of flowers on two blower beds. Note that there are other optimal plantings.

In the second example, there is one flower on each of the flower beds, so the difference is equal to $$$0$$$.