C. Водный баланс
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

$$$n$$$ цистерн с водой стоят в ряд, $$$i$$$-я из них содержит $$$a_i$$$ литров воды. Цистерны пронумерованны от $$$1$$$ до $$$n$$$ слева направо.

Вы можете выполнить следующую операцию: выбрать некоторый подотрезок $$$[l, r]$$$ ($$$1\le l \le r \le n$$$), и перераспределить воду с цистерн $$$l, l+1, \dots, r$$$ между ними равномерно. Другими словами, заменить каждое из $$$a_l, a_{l+1}, \dots, a_r$$$ на $$$\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}$$$. К примеру, если для обьемов $$$[1, 3, 6, 7]$$$ вы выберете $$$l = 2, r = 3$$$, вы получите обьемы $$$[1, 4.5, 4.5, 7]$$$. Вы можете выполнять данную операцию любое количество раз.

Какую лексикографически минимальную последовательность обьемов воды вы можете получить?

Напомним:

Последовательность $$$a$$$ лексикографически меньше последовательности $$$b$$$ равной длины, если и только если выполняется следующее: в первой (слева) позиции, где $$$a$$$ и $$$b$$$ отличаются, в последовательности $$$a$$$ стоит меньший элемент, чем в $$$b$$$.

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество цистерн с водой.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — обьемы воды в цистернах изначально, в литрах.

Из-за большого размера входных данных, не рекомендуется считывать их как doubles.

Выходные данные

Выведите лексикографически минимальную последовательность, которую вы можете получить. В $$$i$$$-й строке выведите итоговый обьем воды в $$$i$$$-й цистерне.

Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка каждого $$$a_i$$$ не превосходит $$$10^{-9}$$$.

Формально, пусть ваш ответ равен $$$a_1, a_2, \dots, a_n$$$, а ответ жюри равен $$$b_1, b_2, \dots, b_n$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$$$ для каждого $$$i$$$.

Примеры
Входные данные
4
7 5 5 7
Выходные данные
5.666666667
5.666666667
5.666666667
7.000000000
Входные данные
5
7 8 8 10 12
Выходные данные
7.000000000
8.000000000
8.000000000
10.000000000
12.000000000
Входные данные
10
3 9 5 5 1 7 5 3 8 7
Выходные данные
3.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
7.500000000
7.500000000
Примечание

В первом примере, вы можете получить лексикографически минимальную последоательность, применив операцию к подотрезку $$$[1, 3]$$$.

Во втором примере, вы не можете получить меньшую лексикографически последовательность.