排列是长度为 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。
示例
输入 #1
9 1 2 3 1 2 1 4 2 5
输出 #1
3 3 1 2 1 2 2 2 3 2
输入 #2
4 4 3 2 1
输出 #2
1 1 1 1 1
输入 #3
4 1 2 2 3
输出 #3
-1
注意
在第一个示例测试中,数组分为三个排列:(2, 1)、(3, 2, 1, 4, 5)、(1, 2)。第一个排列由数组的第二个和第四个元素形成,第二个排列由第三个、第五个、第六个、第七个和第九个元素形成,第三个排列由第一个和第八个元素形成。显然,还有其他可能的分裂变体。