← 返回题目列表

Codeforces · 48/D

D. 排列

中文机器翻译题面 查看原题

排列是长度为 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)。第一个排列由数组的第二个和第四个元素形成,第二个排列由第三个、第五个、第六个、第七个和第九个元素形成,第三个排列由第一个和第八个元素形成。显然,还有其他可能的分裂变体。