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 的朋友,或者
- 鲍勃是每个人的朋友。
第三种情况是不可能解决的,因为第二个人需要和所有人成为朋友,但第一个人却是一个完全陌生的人。