← 返回题目列表

Codeforces · 1157/F

F. 最大平衡圆

中文机器翻译题面 查看原题

一排有 $$$n$$$ 人。第 $$$i$$$ 人的身高是 $$$a_i$$$。你可以选择这些人中的任何一个子集,并尝试将他们安排到一个平衡的圈子中。

一个平衡的圆是这样一种人的顺序,任何相邻人的身高差不超过$$$1$$$。例如,让所选人员的身高为 $$$[a_{i_1}, a_{i_2}, \dots, a_{i_k}]$$$,其中 $$$k$$$ 是您选择的人员数量。那么条件 $$$|a_{i_j} - a_{i_{j + 1}}| \le 1$$$ 应该满足从 $$$1$$$ 到 $$$k-1$$$ 的所有 $$$j$$$ 以及条件 $$$|a_{i_1} - a_{i_k}| \le 1$$$ 应该也满足。 $$$|x|$$$ 表示$$$x$$$ 的绝对值。显然,一个人组成的圆是平衡的。

你的任务是选择最大数量的人,并构建一个由所有选定的人组成的平衡圈。显然,由一个人组成的圆是平衡的,因此答案总是存在的。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 人数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个人的身高。

输出

在输出的第一行打印 $$$k$$$ — 最大平衡圈中的人数。

在第二行中打印 $$$k$$$ 整数 $$$res_1, res_2, \dots, res_k$$$,其中 $$$res_j$$$ 是最大平衡圆中第 $$$j$$$ 人的身高。条件 $$$|res_{j} - res_{j + 1}| \le 1$$$ 应该满足从 $$$1$$$ 到 $$$k-1$$$ 的所有 $$$j$$$ 以及条件 $$$|res_{1} - res_{k}| \le 1$$$ 应该也满足。

示例

输入 #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