#P1157F. Maximum Balanced Circle

    ID: 4750 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>constructive algorithmsdpgreedytwo pointers*2000

Maximum Balanced Circle

No submission language available for this problem.

Description

There are nn people in a row. The height of the ii-th person is aia_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 11. For example, let heights of chosen people be [ai1,ai2,,aik][a_{i_1}, a_{i_2}, \dots, a_{i_k}], where kk is the number of people you choose. Then the condition aijaij+11|a_{i_j} - a_{i_{j + 1}}| \le 1 should be satisfied for all jj from 11 to k1k-1 and the condition ai1aik1|a_{i_1} - a_{i_k}| \le 1 should be also satisfied. x|x| means the absolute value of xx. 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.

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

The second line of the input contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai21051 \le a_i \le 2 \cdot 10^5), where aia_i is the height of the ii-th person.

In the first line of the output print kk — the number of people in the maximum balanced circle.

In the second line print kk integers res1,res2,,reskres_1, res_2, \dots, res_k, where resjres_j is the height of the jj-th person in the maximum balanced circle. The condition resjresj+11|res_{j} - res_{j + 1}| \le 1 should be satisfied for all jj from 11 to k1k-1 and the condition res1resk1|res_{1} - res_{k}| \le 1 should be also satisfied.

Input

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

The second line of the input contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai21051 \le a_i \le 2 \cdot 10^5), where aia_i is the height of the ii-th person.

Output

In the first line of the output print kk — the number of people in the maximum balanced circle.

In the second line print kk integers res1,res2,,reskres_1, res_2, \dots, res_k, where resjres_j is the height of the jj-th person in the maximum balanced circle. The condition resjresj+11|res_{j} - res_{j + 1}| \le 1 should be satisfied for all jj from 11 to k1k-1 and the condition res1resk1|res_{1} - res_{k}| \le 1 should be also satisfied.

Samples

Sample Input 1

7
4 3 5 1 2 2 1

Sample Output 1

5
2 1 1 2 3

Sample Input 2

5
3 7 5 1 5

Sample Output 2

2
5 5

Sample Input 3

3
5 1 4

Sample Output 3

2
4 5

Sample Input 4

7
2 2 3 2 1 2 2

Sample Output 4

7
1 2 2 2 2 3 2