2155. Приблизительно

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

В результате расшифровки с применением всех известных в королевстве колдовских заклинаний удалось получить лишь последовательность целых чисел `a_1,\ a_2,\ …,\ a_n`. Тогда король повелел найти наиболее похожую на данную неубывающую последовательность вещественных чисел `b_1,\ b_2,\ …,\ b_n`. Посовещавшись, придворные мудрецы решили найти такую последовательность, чтобы величина

была как можно меньше.

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

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

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

5
5 4 3 2 1

3 3 3 3 3

9
3 2 1 8 6 4 9 7 5

2.0 2.0 2.0 6.0 6.0 6.0 7.0 7.0 7.0