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