← 返回题目列表

Codeforces · 1091/E

E. 新年和熟人估计

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

Bob 是社交网络 Faithbug 的活跃用户。在这个网络上,人们能够建立相互的友谊。也就是说,如果 $$$a$$$ 是 $$$b$$$ 的好友,那么 $$$b$$$ 也是 $$$a$$$ 的好友。因此,每个用户都有非负数量的朋友。

今天早上,有人匿名向 Bob 发送了以下链接:图实现问题,Bob 想知道那人是谁。为此,他首先需要了解社交网络是什么样的。他调查了网络上所有其他人的个人资料,并记下了他朋友的数量。然而,他忘记记下他的朋友人数。帮助他找出他有多少朋友。由于可能有很多可能的答案,因此请打印所有答案。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$),即网络上除 Bob 之外的人数。

第二行包含 $$$n$$$ 数字 $$$a_1,a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq n$$$),其中 $$$a_i$$$ 是 $$$i$$$ 是该人的朋友的人数。

输出

打印 $$$a_{n+1}$$$ 的所有可能值 — Bob 可以成为朋友的人数(按升序排列)。

如果不存在解,则输出$$$-1$$$。

示例

输入 #1

3
3 3 3

输出 #1

3

输入 #2

4
1 1 1 1

输出 #2

0 2 4

输入 #3

2
0 2

输出 #3

-1

输入#4

35
21 26 18 4 28 2 15 13 16 25 6 32 11 5 31 17 9 3 24 33 14 27 29 1 20 4 12 7 10 30 34 8 19 23 22

输出#4

13 15 17 19 21

注意

在第一个测试用例中,唯一的解决方案是每个人都是每个人的朋友。这就是为什么鲍勃应该有 $$$3$$$ 朋友。

在第二个测试用例中,存在三种可能的解决方案(除了对称性之外):

- $$$a$$$ 是 $$$b$$$ 的朋友,$$$c$$$ 是 $$$d$$$ 的朋友,而 Bob 没有朋友,或者
- $$$a$$$ 是 $$$b$$$ 的朋友,并且 $$$c$$$ 和 $$$d$$$ 都是 Bob 的朋友,或者
- 鲍勃是每个人的朋友。

第三种情况是不可能解决的,因为第二个人需要和所有人成为朋友,但第一个人却是一个完全陌生的人。