一排有 $$$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$$$) — 水箱中的初始水量,以升为单位。
由于输入较大,不建议将输入读取为双倍。
输出
打印你能得到的按字典顺序排列的最小序列。在第 $$$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
4 7 5 5 7
输出 #1
5.666666667 5.666666667 5.666666667 7.000000000
输入 #2
5 7 8 8 10 12
输出 #2
7.000000000 8.000000000 8.000000000 10.000000000 12.000000000
输入 #3
10 3 9 5 5 1 7 5 3 8 7
输出 #3
3.000000000 5.000000000 5.000000000 5.000000000 5.000000000 5.000000000 5.000000000 5.000000000 7.500000000 7.500000000
注意
在第一个示例中,您可以通过对子段 $$$[1, 3]$$$ 进行运算来获取序列。
在第二个示例中,您无法获得任何字典顺序较小的序列。