Задача "Минимизировать количество взрослых"

Будем называть элемент массива "взрослым", если он строго больше обоих своих соседей. Первый и последний элементы массива не могут быть "взрослыми" по определению.

Вам дан массив. Требуется таким образом переставить в нем элементы, чтобы количество "взрослых" элементов оказалост как можно меньше.

Задано сначала число N (1≤N≤100), а затем N целых чисел, по модулю не превышающих 1000.

Выведите эти N чисел таком порядке, чтобы количество "взрослых" элементов было минимально возможным..

Пример вводаПример выводаПояснение
5
3 1 2 4 2
4 3 2 2 1
В приведенной в примере вывода расстановке нет ни одного "взрослого" элемента