Задача M. Забор по фен-шую

Автор:А. Кленин, Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:105  

Условие

Марфа Геннадьевна попросила внука построить новый забор вдоль огорода. Внук выполнил просьбу бабушки и построил забор из N досок, в котором доска с номером i имела высоту ai сантиметров.

Марфа Геннадьевна недавно прочитала книгу, в которой было написано, что гармоничным является забор, состоящий из чередующихся высоких и низких деревянных досок, то есть должно выполняться либо условие a1 < a2 > a3 < a4 > …, либо условие a1 > a2 < a3 > a4 < ….

Внук решил порадовать Марфу Геннадьевну и нарастить некоторые доски, чтобы сделать забор гармоничным. При этом ему хочется потратить поменьше древесины.

Напишите программу, которая по указанным длинам досок ai определяет новый набор длин bi, в котором:

  1. ai ≤ bi,
  2. либо b1 < b2 > b3 < b4 > …, либо b1 > b2 < b3 > b4 < …
  3. сумма bi минимальна.

Формат входного файла

Входной файл содержит целое число N за которым следует N чисел ai — длины досок.

Формат выходного файла

Входной файл должен содержать N целых чисел bi — новые длины досок. Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 100; 1 ≤ ai ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
20
20
2
4
11 10 11 15
11 12 11 15

0.125s 0.029s 15