← 返回题目列表

Codeforces · 1081/B

B. 欢送会

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

Couti 和他的同学很快就要上大学了。为了互相告别,班级策划了一场盛大的欢送会,同学、老师、家长载歌载舞。

Couti 记得有 $$$n$$$ 人参加了那个聚会。为了让聚会变得更有趣,每个人都戴着 $$$n$$$ 种奇怪帽子中的一顶帽子,编号为 $$$1、2、\ldots n$$$。可能有几个人戴着同一种帽子。有些种类的帽子可能无人认领。

聚会结束后,第 $$$i$$$ 人说有 $$$a_i$$$ 人戴着与他自己不同的帽子。

已经好几天了,Couti 已经忘记了别人的帽子,但他对此很好奇。令 $$$b_i$$$ 为第 $$$i$$$ 个人所戴的帽子类型的数量,Couti 希望你找到任何可能的 $$$b_1, b_2, \ldots, b_n$$$ 与任何人的陈述都不矛盾。因为有些人记忆力可能不好,根本就没有办法。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),即队伍中的人数。

第二行包含$$$n$$$整数$$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n-1$$$),人的陈述。

输出

如果没有解决方案,则打印一行“Impossible”。

否则,打印“可能”,然后打印 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$)。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
0 0 0

输出 #1

Possible
1 1 1

输入 #2

5
3 3 2 2 2

输出 #2

Possible
1 1 2 2 2

输入 #3

4
0 1 2 3

输出 #3

Impossible

注意

在第一个例子的答案中,所有帽子都是一样的,所以每个人都会说没有人戴着与 $$$1$$$ 不同的帽子。

在第二个示例的答案中,第一个人和第二个人戴着 $$$1$$$ 类型的帽子,其他所有人都戴着 $$$2$$$ 类型的帽子。

所以前两个人会说有三个人的帽子与他们自己的不同。同样,最后三个人会说有两个人戴着与他们自己不同的帽子。

在第三个示例中,可以证明不存在解。

在第一和第二示例中,其他可能的配置也是可能的。