CF1299C Water Balance

有 $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$。

第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示水箱的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$），表示每个水箱初始的水量（单位：升）。 由于输入数据较大，不建议将输入读入为 double 类型。

输出你能得到的字典序最小的水量序列。第 $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}$ 时，你的答案才会被接受。

在第一个样例中，你可以通过对子区间 $[1, 3]$ 进行操作得到答案。 在第二个样例中，无法得到更小的字典序序列。 由 ChatGPT 4.1 翻译