B. Julia and Flower Beds
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юля переезжает в свой новый дом! В саду на новом месте есть две клумбы, в которых пока что нет цветов. В ближайшем цветочном магазине «Инноцвет» есть $$$n$$$ видов цветов, пронумерованных числами от $$$1$$$ до $$$n$$$.

Юля уже купила все цветы, которые планирует посадить: цветов вида $$$i$$$ было куплено ровно $$$a_i$$$ штук. При этом, дабы сделать дизайн разнообразным, Юля ограничила количество цветов следующим образом: цветов вида $$$i$$$ было куплено не менее одного и не более $$$i$$$ (то есть $$$1 \le a_i \le i$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$).

Юля хочет рассадить все цветы по двум клумбам наиболее красивым образом. Для гармонии, цветы одного вида она будет сажать только в одну клумбу (все цветы одного вида должны быть высажены либо на первой клумбе, либо на второй клумбе). При этом, чтобы обеспечить максимальную симметрию, Юля хочет, чтобы число цветов на первой и второй клумбах отличалось как можно меньше.

Так как новоселье уже очень скоро, помогите Юле найти требуемую рассадку цветов!

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — число различных видов цветов в магазине «Инноцвет».

Во второй строке находятся $$$n$$$ чисел $$$a_i$$$ ($$$1 \le a_i \le i$$$) — число купленных цветов каждого вида.

Выходные данные

В первой строке выведите одно целое неотрицательное число — минимальную разность количеств цветов на клумбах.

Во второй строке выведите рассадку цветов в следующем формате: $$$n$$$ чисел $$$w_1, \ldots, w_n$$$, где $$$w_i = 1$$$, если цветы вида $$$i$$$ нужно посадить в первую клумбу, и $$$w_i = 2$$$ в противном случае.

Если существует несколько рассадок с минимальной разностью количеств цветов, выведите любую.

Система оценки
ПодзадачаБаллыОграничения
115$$$a_i = i$$$
220$$$n \le 16$$$
325$$$n \le 100$$$
440$$$n \le 2 \cdot 10^5$$$
Примеры
Входные данные
5
1 2 1 4 3
Выходные данные
1
1 2 1 1 2
Входные данные
2
1 1
Выходные данные
0
2 1
Примечание

В первом примере, на первой клумбе посажено $$$1+1+4=6$$$ цветков, а на второй — $$$2+3=5$$$ цветков, и разность количеств цветов равна $$$1$$$. Получить одинаковое количество цветов в первой и второй клумбе невозможно. Заметим, что в этом примере есть и другие оптимальные рассадки.

Во втором примере на каждой клумбе посажен один цветок, и минимальная разность равна $$$0$$$.