CF48D.Permutations

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once. For example, (1), (4, 3, 5, 1, 2), (3, 2, 1) are permutations, and (1, 1), (4, 3, 1), (2, 3, 4) are not.

There are many tasks on permutations. Today you are going to solve one of them. Let’s imagine that somebody took several permutations (perhaps, with a different number of elements), wrote them down consecutively as one array and then shuffled the resulting array. The task is to restore the initial permutations if it is possible.

排列是指由 $1$ 到 $n$ 的整数组成、长度为 $n$ 且每个数恰好出现一次的序列。例如，$(1)$、$(4,\,3,\,5,\,1,\,2)$、$(3,\,2,\,1)$ 是排列，而 $(1,\,1)$、$(4,\,3,\,1)$、$(2,\,3,\,4)$ 不是。

关于排列有许多问题。今天你将解决其中一道。试想：某人取了若干个排列（这些排列的长度可能各不相同），将它们依次写成一个数组，然后对这个数组进行了随机打乱。你的任务是：若可能，则还原出最初的那些排列。

The first line contains an integer n (1 ≤ n ≤ 105). The next line contains the mixed array of n integers, divided with a single space. The numbers in the array are from 1 to 105.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。下一行包含由单个空格分隔的 $n$ 个整数组成的混合数组。数组中的数字范围为 $1$ 到 $10^5$。

If this array can be split into several permutations so that every element of the array belongs to exactly one permutation, print in the first line the number of permutations. The second line should contain n numbers, corresponding to the elements of the given array. If the i-th element belongs to the first permutation, the i-th number should be 1, if it belongs to the second one, then its number should be 2 and so on. The order of the permutations’ numbering is free.

If several solutions are possible, print any one of them. If there’s no solution, print in the first line  - 1.

如果该数组可以被划分为若干个排列，使得数组中的每个元素恰好属于其中一个排列，则在第一行输出排列的个数。第二行应包含 $n$ 个数字，对应于给定数组的各元素：若第 $i$ 个元素属于第一个排列，则第 $i$ 个数字应为 1；若属于第二个排列，则应为 2，依此类推。排列编号的顺序可任意。

若存在多种可行解，输出任意一种即可。若不存在解，则在第一行输出 -1。

In the first sample test the array is split into three permutations: (2, 1), (3, 2, 1, 4, 5), (1, 2). The first permutation is formed by the second and the fourth elements of the array, the second one — by the third, the fifth, the sixth, the seventh and the ninth elements, the third one — by the first and the eigth elements. Clearly, there are other splitting variants possible.

在第一个样例测试中，该数组被划分为三个排列：$(2,\,1)$、$(3,\,2,\,1,\,4,\,5)$、$(1,\,2)$。第一个排列由数组的第 2 个和第 4 个元素构成，第二个排列由数组的第 3、第 5、第 6、第 7 和第 9 个元素构成，第三个排列由数组的第 1 个和第 8 个元素构成。显然，还存在其他可能的划分方式。