D2. День рождения Сажи (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Различие между версиями заключается в том, что в простой версии все $$$a_i$$$ различны. Вы можете делать взломы, только если обе версии задачи сданы.

Сегодня у Сажи день рождения, и она пойдёт в магазин покупать ледяные сферы. Все $$$n$$$ ледяных сфер стоят в магазине в ряд на одной полке и пронумерованы целыми числами от $$$1$$$ до $$$n$$$ слева направо. У каждой ледяной сферы есть цена — положительное целое число. Некоторые сферы могут иметь одинаковую цену.

Ледяная сфера считается дешёвой, если она стоит строго меньше, чем две соседние: ближайшая справа и ближайшая слева. Крайняя слева и крайняя справа ледяные сферы не считаются дешёвыми. Сажа сначала выберет все дешёвые ледяные сферы, а потом купит только их.

Вы можете прийти в магазин до Сажи и переставить ледяные сферы так, как хотите. Узнайте, какое максимальное количество ледяных сфер Сажа может купить, и покажите, как для этого переставить сферы.

Входные данные

В первой строке находится единственное целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество ледяных сфер в магазине.

Во второй строке находится $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — цены ледяных сфер.

Выходные данные

В первой строке выведите максимальное количество ледяных сфер, которое может купить Сажа.

Во второй строке выведите цены ледяных сфер в том порядке, в котором их нужно поставить на полку. Если возможных ответов несколько, выведите любой из них.

Пример
Входные данные
7
1 3 2 2 4 5 4
Выходные данные
3
3 1 4 2 4 2 5
Примечание

В тесте из условия невозможно расставить ледяные сферы так, чтобы Сажа купила $$$4$$$ из них. Если расставить сферы в порядке $$$(3, 1, 4, 2, 4, 2, 5)$$$, то Сажа купит одну сферу за $$$1$$$ и две сферы по $$$2$$$.