New Year and the Acquaintance Estimation
Contest: Good Bye 2018
Difficulty rating: 2400
Tags: binary search, data structures, graphs, greedy, implementation, math, sortings

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 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.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
3 3 3

Example output:
3

Example input:
4
1 1 1 1

Example output:
0 2 4

Editorial:
The first observation is that using the Handshaking lemma, we know the parity of $$$a_{n+1}$$$.
Secondly, on the integers of same parity, the answer always forms a continuous interval, that is if $$$a_{n+1} = X$$$ is one possible answer and $$$a_{n+1} = Y$$$ is another with $$$X < Y$$$, then every $$$X < Z < Y$$$ satisfying $$$X \bmod 2 == Z \bmod 2$$$ is also an answer. We should thus look into some binary search approaches.
We use the Erdos-Gallai theorem linked in the statement to determine whether a sequence is graphic. If it is not the case, we must determine whether the answer is too big or too small. This depends on whether the $$$a_{n+1}$$$ is on the left or the right side of the inequality when it is not satisfied. If it is on the left, it means that it is too big – clearly making it larger is never going to change the sign of the inequality. On the contrary, if $$$a_{n+1}$$$ is on the right, it is clearly too small.
It can also happen that the inequality is false for some $$$k$$$ where $$$a_{n+1}$$$ is on the left and for some other $$$k$$$ it is on the right. Then there clearly is no solution.
Checking the inequality naively takes $$$\mathcal O(n^2)$$$ time, but we can also do it in $$$\mathcal O(n)$$$: for left side we need a prefix sum, and for right side we maintain the sum and also how many times a particular value occurs. The sum of values at most $$$k$$$ can then be maintained in $$$\mathcal O(1)$$$. This yields an algorithm in $$$\mathcal O(n \log n)$$$.
Alternatively, we can perform a similar binary search using Havel-Hakimi algorithm, using a segment tree or a multiset and tracking whether the $$$a_{n+1}$$$ was already processed or not to find out whether the answer is too small or too big. This yields $$$\mathcal O(n \log^2 n)$$$ algorithm.