306175: CF1157F. Maximum Balanced Circle

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Maximum Balanced Circle

题意翻译

输入k个数,构造一个最大(大小为n)的环,环上任意abs(a[(i+1)%n]-a[i])<=1。

题目描述

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.

输入输出格式

输入格式


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.

输出格式


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.

输入输出样例

输入样例 #1

7
4 3 5 1 2 2 1

输出样例 #1

5
2 1 1 2 3

输入样例 #2

5
3 7 5 1 5

输出样例 #2

2
5 5 

输入样例 #3

3
5 1 4

输出样例 #3

2
4 5 

输入样例 #4

7
2 2 3 2 1 2 2

输出样例 #4

7
1 2 2 2 2 3 2 

Input

题意翻译

输入k个数,构造一个最大(大小为n)的环,环上任意abs(a[(i+1)%n]-a[i])<=1。

加入题单

上一题 下一题 算法标签: