Codeforces Round 555 (Div. 3) |
---|
Закончено |
В ряду стоит $$$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$$$ для всех $$$j$$$ от $$$1$$$ до $$$k-1$$$, а также должно выполняться условие $$$|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$$$ для всех $$$j$$$ от $$$1$$$ до $$$k-1$$$, а также должно выполняться условие $$$|res_{1} - res_{k}| \le 1$$$.
7 4 3 5 1 2 2 1
5 2 1 1 2 3
5 3 7 5 1 5
2 5 5
3 5 1 4
2 4 5
7 2 2 3 2 1 2 2
7 1 2 2 2 2 3 2
Название |
---|