CF1299C.Water Balance

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$.

一行中有 $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$ 中对应元素时，称序列 $a$ 的字典序小于序列 $b$。

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.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 水箱的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）—— 各水箱的初始水量（单位：升）。

由于输入规模较大，不建议将输入读取为浮点数（double）。

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$.

输出你能得到的字典序最小的序列。在第 $i$ 行输出第 $i$ 个水箱中的最终水量。

若每个 $a_i$ 的绝对误差或相对误差均不超过 $10^{-9}$，则你的答案视为正确。

形式化地，设你的答案为 $a_1, a_2, \dots, a_n$，评测机的答案为 $b_1, b_2, \dots, b_n$。当且仅当对每个 $i$ 均满足 $\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$ 时，你的答案被接受。

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.

在第一个样例中，你可以通过对子段 $[1, 3]$ 应用该操作来得到该序列。

在第二个样例中，你无法得到任何字典序更小的序列。