Maximum Balanced Circle
Contest: Codeforces Round 555 (Div. 3)
Difficulty rating: 2000
Tags: constructive algorithms, dp, greedy, two pointers

There are $$$n$$$ people in a row. The height of the $$$i$$$-th person is $$$a_i$$$. You can choose any subset of these people and try to arrange them into a balanced circle.

A balanced circle is such an order of people that the difference between heights of any adjacent people is no more than $$$1$$$. For example, let heights of chosen people be $$$[a_{i_1}, a_{i_2}, \dots, a_{i_k}]$$$, where $$$k$$$ is the number of people you choose. Then the condition $$$|a_{i_j} - a_{i_{j + 1}}| \le 1$$$ should be satisfied for all $$$j$$$ from $$$1$$$ to $$$k-1$$$ and the condition $$$|a_{i_1} - a_{i_k}| \le 1$$$ should be also satisfied. $$$|x|$$$ means the absolute value of $$$x$$$. It is obvious that the circle consisting of one person is balanced.

Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of people.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the height of the $$$i$$$-th person.

Output format:
In the first line of the output print $$$k$$$ — the number of people in the maximum balanced circle.

In the second line print $$$k$$$ integers $$$res_1, res_2, \dots, res_k$$$, where $$$res_j$$$ is the height of the $$$j$$$-th person in the maximum balanced circle. The condition $$$|res_{j} - res_{j + 1}| \le 1$$$ should be satisfied for all $$$j$$$ from $$$1$$$ to $$$k-1$$$ and the condition $$$|res_{1} - res_{k}| \le 1$$$ should be also satisfied.

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

Example input:
7
4 3 5 1 2 2 1

Example output:
5
2 1 1 2 3

Example input:
5
3 7 5 1 5

Example output:
2
5 5

Editorial:
Let's realize what we need to construct the minimum balanced circle with heights from $$$l$$$ to $$$r$$$. We can represent it as $$$l, l + 1, \dots, r - 1, r, r - 1, \dots, l + 1$$$. As we can see, we need one occurrence of $$$l$$$ and $$$r$$$ and two occurrences of all other heights from $$$l + 1$$$ to $$$r - 1$$$. How can we find the maximum balanced circle using this information? We can find the maximum by inclusion segment of neighboring heights with at least two occurrences using the array of frequencies $$$cnt$$$, sorted array of unique heights $$$b$$$ and two pointers technique. For the current left border $$$l$$$ we should increase $$$r$$$ (initially it is $$$l + 1$$$ and it is an excluded border) while $$$b_r - b_{r - 1}=1$$$ and $$$cnt_{b_r} \ge 2$$$. Then for the current left and right borders we can try to extend the segment to the left if $$$b_l - b_{l - 1} = 1$$$ and to the right if $$$b_{r + 1} - b_r = 1$$$ and try to update the answer with the the current segment (and go to the next segment). There may be some corner cases like $$$n = 1$$$ or all $$$cnt$$$ are $$$1$$$, but you can avoid them if you will implement the solution carefully. There are almost no corner cases in my solution, you can see details of implementation in authors code.
Time complexity: $$$O(n \log n)$$$ or $$$O(n)$$$ (depends on sorting method).