Это сложная версия задачи. Различие между версиями заключается в том, что в простой версии все \(a_i\) различны. Вы можете делать взломы, только если обе версии задачи сданы.
Сегодня у Сажи день рождения, и она пойдёт в магазин покупать ледяные сферы. Все \(n\) ледяных сфер стоят в магазине в ряд на одной полке и пронумерованы целыми числами от \(1\) до \(n\) слева направо. У каждой ледяной сферы есть цена — положительное целое число. Некоторые сферы могут иметь одинаковую цену.
Ледяная сфера считается дешёвой, если она стоит строго меньше, чем две соседние: ближайшая справа и ближайшая слева. Крайняя слева и крайняя справа ледяные сферы не считаются дешёвыми. Сажа сначала выберет все дешёвые ледяные сферы, а потом купит только их.
Вы можете прийти в магазин до Сажи и переставить ледяные сферы так, как хотите. Узнайте, какое максимальное количество ледяных сфер Сажа может купить, и покажите, как для этого переставить сферы.
Выходные данные
В первой строке выведите максимальное количество ледяных сфер, которое может купить Сажа.
Во второй строке выведите цены ледяных сфер в том порядке, в котором их нужно поставить на полку. Если возможных ответов несколько, выведите любой из них.
Примечание
В тесте из условия невозможно расставить ледяные сферы так, чтобы Сажа купила \(4\) из них. Если расставить сферы в порядке \((3, 1, 4, 2, 4, 2, 5)\), то Сажа купит одну сферу за \(1\) и две сферы по \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1 3 2 2 4 5 4
|
3
3 1 4 2 4 2 5
|