Задача B3. Новогодний код

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

Условие

Деду Морозу из Нью-Васюков пишут не стихи, а проги. Дед Мороз любит, когда код программы похож на его бороду, то есть длины строк кода {ai}Ni = 1 удовлетворяют условию

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.122s 0.026s 17