D. Перестановки
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Перестановка — это последовательность длины n целых чисел от 1 до n, в которой все числа встречаются ровно по одному разу. Например, (1), (4, 3, 5, 1, 2), (3, 2, 1) — перестановки, а (1, 1), (4, 3, 1), (2, 3, 4) — нет.

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

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

В первой строке содержится целое число n (1 ≤ n ≤ 105). Следующая строка содержит перемешанную последовательность из n целых чисел, разделенных одиночными пробелами. Числа в последовательности от 1 до 105.

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

Если данную последовательность можно разбить на несколько перестановок так, что каждый элемент последовательности принадлежит в точности одной перестановке, в первой строке выведите количество получившихся перестановок. Вторая строка должна содержать n чисел, соответствующих элементам заданной последовательности. Если i-й элемент относится к первой перестановке, то i-е число должно быть 1, если ко второй — то 2, и т.д. Порядок нумерации перестановок произволен.

Если решений несколько, выведите любое. Если решения не существует, выведите в первой строке  - 1.

Примеры
Входные данные
9
1 2 3 1 2 1 4 2 5
Выходные данные
3
3 1 2 1 2 2 2 3 2
Входные данные
4
4 3 2 1
Выходные данные
1
1 1 1 1
Входные данные
4
1 2 2 3
Выходные данные
-1
Примечание

В первом примере последовательность разбивается на три перестановки: (2, 1), (3, 2, 1, 4, 5), (1, 2). Первая перестановка образована вторым и четвертым элементами последовательности, вторая — третьим, пятым, шестым, седьмым и девятым элементами, третья — первым и восьмым элементами. Ясно, что возможны и другие варианты разбиения.