Water Balance
Contest: Codeforces Round 618 (Div. 1)
Difficulty rating: 2100
Tags: data structures, geometry, greedy

There are $$$n$$$ water tanks in a row, $$$i$$$-th of them contains $$$a_i$$$ liters of water. The tanks are numbered from $$$1$$$ to $$$n$$$ from left to right.

You can perform the following operation: choose some subsegment $$$[l, r]$$$ ($$$1\le l \le r \le n$$$), and redistribute water in tanks $$$l, l+1, \dots, r$$$ evenly. In other words, replace each of $$$a_l, a_{l+1}, \dots, a_r$$$ by $$$\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}$$$. For example, if for volumes $$$[1, 3, 6, 7]$$$ you choose $$$l = 2, r = 3$$$, new volumes of water will be $$$[1, 4.5, 4.5, 7]$$$. You can perform this operation any number of times.

What is the lexicographically smallest sequence of volumes of water that you can achieve?

As a reminder:

A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ of the same length if and only if the following holds: in the first (leftmost) position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of water tanks.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — initial volumes of water in the water tanks, in liters.

Because of large input, reading input as doubles is not recommended.

Output format:
Print the lexicographically smallest sequence you can get. In the $$$i$$$-th line print the final volume of water in the $$$i$$$-th tank.

Your answer is considered correct if the absolute or relative error of each $$$a_i$$$ does not exceed $$$10^{-9}$$$.

Formally, let your answer be $$$a_1, a_2, \dots, a_n$$$, and the jury's answer be $$$b_1, b_2, \dots, b_n$$$. Your answer is accepted if and only if $$$\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$$$ for each $$$i$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample, you can get the sequence by applying the operation for subsegment $$$[1, 3]$$$.

In the second sample, you can't get any lexicographically smaller sequence.

Example input:
4
7 5 5 7

Example output:
5.666666667
5.666666667
5.666666667
7.000000000

Example input:
5
7 8 8 10 12

Example output:
7.000000000
8.000000000
8.000000000
10.000000000
12.000000000

Editorial:
Let's try to make the operation simpler. When we apply the operation, only the sum of the segment matters. And so let's instead define the operation on prefix sum array:
Replace each of $$$p_l, p_{l+1}, \dots, p_r$$$ by $$$p_i = p_{l-1} + \frac{p_r - p_{l - 1} }{r-l+1} \cdot (i - l + 1)$$$. You may see how similar it is to a line function. Hence we get the idea to plot points $$$(i, p_i)$$$ ($$$(0, p_0 = 0)$$$ included), and our operation is just drawing a line between $$$2$$$ points on integer $$$x$$$ coordinates.
Nicely if sequence $$$a$$$ is lexicographically smaller than sequence $$$b$$$, then prefix sum array of $$$a$$$ is smaller than prefix sum array of $$$b$$$.
So we need to find the lexicographically smallest array $$$p$$$. And then it is easy to see the lexicographically smallest sequence $$$p$$$ will be the lower part of the convex hull.
If you're interested you can solve IMO 2018 SL A4 by plotting similar points. I have written my solutionhere