29521번 - Приблизительно 스페셜 저지다국어

Однажды королевский шпион Цилритш решил отправить королю послание. Он закодировал его в виде неубывающей последовательности вещественных чисел, записал на куске кожи единорога и отправил почтовым голубем. К сожалению, голубь оказался поражен стрелой злого орка и упал в болото. Слуги короля нашли послание, но оно оказалось испорчено водой и прочитать его оказалось непросто.

В результате расшифровки с применением всех известных в королевстве колдовских заклинаний удалось получить лишь последовательность целых чисел $a_1, a_2, \ldots, a_n$. Тогда король повелел найти наиболее похожую на данную неубывающую последовательность вещественных чисел $b_1, b_2, \ldots, b_n$. Посовещавшись, придворные мудрецы решили найти такую последовательность, чтобы величина $$s = \sum_{i=1}^n (a_i-b_i)^2$$ была как можно меньше.

Помогите им найти такую последовательность.

Первая строка входного файла содержит $n$ --- длину полученной последовательности. Вторая строка содержит $n$ целых чисел: $a_1, a_2, \ldots, a_n$ ($1 \le n \le 200\,000$, $1 \le a_i \le 10^6$).

Выведите $n$ чисел: самую похожую на заданную во входном файле неубывающую последовательность. Если решений несколько, выведите любое. В вашем ответе величина $s$ должна иметь либо абсолютную, либо относительную погрешность не больше $10^{-9}$. Это означает, что если ваш ответ $a$, а правильный ответ $b$, величина $|a-b|/\max(b, 1)$ не должна превышать $10^{-9}$.