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

Условие

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

a₁ < a₂ > a₃ < a₄ > …    ∧   a₁ > a₂ < a₃ > a₄ < ….

Коля решил порадовать Деда Мороза и нарастить некоторые строки кода пробелами и комментариями, чтобы код напоминал Деду Морозу его бороду. Коля хочет добавить в код как можно меньше символов.

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

1. a_i ≤ b_i,
2. либо b₁ < b₂ > b₃ < b₄ > …, либо b₁ > b₂ < b₃ > b₄ < …
3. сумма b_i минимальна.

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

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

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

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

Ограничения

1 ≤ N ≤ 100; 1 ≤ a_i ≤ 100

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

1
20

20

4
11 10 11 15

11 12 11 15