\(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\).
Выходные данные
Выведите лексикографически минимальную последовательность, которую вы можете получить. В \(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\).
Примечание
В первом примере, вы можете получить лексикографически минимальную последоательность, применив операцию к подотрезку \([1, 3]\).
Во втором примере, вы не можете получить меньшую лексикографически последовательность.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7 5 5 7
|
5.666666667
5.666666667
5.666666667
7.000000000
|
|
2
|
5
7 8 8 10 12
|
7.000000000
8.000000000
8.000000000
10.000000000
12.000000000
|
|
3
|
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
|