New Year and the Acquaintance Estimation

题意翻译

## 题目描述 Bob是社交网站`FaithBug`上的一名活跃用户。在这个网站上，人们之间的友情是相互的。这就是说，如果 $a$ 是 $b$ 的一个朋友，那么 $b$ 也是 $a$ 的一个朋友。因此，每个用户都有不小于 $0$ 个朋友。 这个早晨，一个匿名用户给Bob发送了这个链接：[graph realization problem](https://en.wikipedia.org/wiki/Graph_realization_problem)。Bob想要知道那人是谁。为了知道这件事，他首先得知道这个社交网络的形态。他查看了网站上所有其他人的个人信息，并且记下了他们的朋友数量。然而，他忘了记下自己的朋友数量！请帮他计算他可能的朋友数量。如果有多解，全部输出。 简化版：给出一个长度为 $n$ 的度数序列，问是否存在一个大小为 $n+1$ 的简单无向图，满足给定的度数序列是这个图的度数序列的前缀。 ## 输入输出格式 ### 输入格式 第一行是一个整数 $n$ ，表示这个社交网站上的人数，不及Bob。 第二行有 $n$ 个数 $a_1,a_2,\ldots,a_n$ ，其中 $a_i$ 表示第 $i$ 个人的朋友数量。 ### 输出格式 升序输出所有可能的 $a_{n+1}$ ，代表Bob可能拥有的朋友个数。 如果无解，输出一行`-1`。 ## 数据范围 $1\leq n\leq 5\times 10^5, 0\leq a_i\leq n$ ## 说明 第一个样例中，唯一的可能情况是，每个人都是所有其他人的朋友。因此，Bob有三个朋友。 第二个样例中，有三种可能的非等价情况： 1. $a$ 是 $b$ 的朋友， $c$ 是 $d$ 的朋友，然而Bob没有朋友。 2. $a$ 是 $b$ 的朋友， $c$ 和 $d$ 都是Bob的朋友。 3. Bob是所有人的朋友。 第三个样例是不可能的，因为第二个人应该是所有人的朋友，然而第一个人却没有朋友。

题目描述

Bob is an active user of the social network Faithbug. On this network, people are able to engage in a mutual friendship. That is, if $ a $ is a friend of $ b $ , then $ b $ is also a friend of $ a $ . Each user thus has a non-negative amount of friends. This morning, somebody anonymously sent Bob the following link: [graph realization problem](https://en.wikipedia.org/wiki/Graph_realization_problem) and Bob wants to know who that was. In order to do that, he first needs to know how the social network looks like. He investigated the profile of every other person on the network and noted down the number of his friends. However, he neglected to note down the number of his friends. Help him find out how many friends he has. Since there may be many possible answers, print all of them.

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \leq n \leq 5 \cdot 10^5 $ ), the number of people on the network excluding Bob. The second line contains $ n $ numbers $ a_1,a_2, \dots, a_n $ ( $ 0 \leq a_i \leq n $ ), with $ a_i $ being the number of people that person $ i $ is a friend of.

输出格式

Print all possible values of $ a_{n+1} $ — the amount of people that Bob can be friend of, in increasing order. If no solution exists, output $ -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 

说明

In the first test case, the only solution is that everyone is friends with everyone. That is why Bob should have $ 3 $ friends. In the second test case, there are three possible solutions (apart from symmetries): - $ a $ is friend of $ b $ , $ c $ is friend of $ d $ , and Bob has no friends, or - $ a $ is a friend of $ b $ and both $ c $ and $ d $ are friends with Bob, or - Bob is friends of everyone. The third case is impossible to solve, as the second person needs to be a friend with everybody, but the first one is a complete stranger.

题意翻译

## 题目描述 Bob是社交网站`FaithBug`上的一名活跃用户。在这个网站上，人们之间的友情是相互的。这就是说，如果 $a$ 是 $b$ 的一个朋友，那么 $b$ 也是 $a$ 的一个朋友。因此，每个用户都有不小于 $0$ 个朋友。 这个早晨，一个匿名用户给Bob发送了这个链接：[graph realization problem](https://en.wikipedia.org/wiki/Graph_realization_problem)。Bob想要知道那人是谁。为了知道这件事，他首先得知道这个社交网络的形态。他查看了网站上所有其他人的个人信息，并且记下了他们的朋友数量。然而，他忘了记下自己的朋友数量！请帮他计算他可能的朋友数量。如果有多解，全部输出。 简化版：给出一个长度为 $n$ 的度数序列，问是否存在一个大小为 $n+1$ 的简单无向图，满足给定的度数序列是这个图的度数序列的前缀。 ## 输入输出格式 ### 输入格式 第一行是一个整数 $n$ ，表示这个社交网站上的人数，不及Bob。 第二行有 $n$ 个数 $a_1,a_2,\ldots,a_n$ ，其中 $a_i$ 表示第 $i$ 个人的朋友数量。 ### 输出格式 升序输出所有可能的 $a_{n+1}$ ，代表Bob可能拥有的朋友个数。 如果无解，输出一行`-1`。 ## 数据范围 $1\leq n\leq 5\times 10^5, 0\leq a_i\leq n$ ## 说明 第一个样例中，唯一的可能情况是，每个人都是所有其他人的朋友。因此，Bob有三个朋友。 第二个样例中，有三种可能的非等价情况： 1. $a$ 是 $b$ 的朋友， $c$ 是 $d$ 的朋友，然而Bob没有朋友。 2. $a$ 是 $b$ 的朋友， $c$ 和 $d$ 都是Bob的朋友。 3. Bob是所有人的朋友。 第三个样例是不可能的，因为第二个人应该是所有人的朋友，然而第一个人却没有朋友。