# E. Water Balance

Codeforces Round 618 (Div. 2) E. Water Balance

## Description

There are n water tanks in a row, i-th of them contains ai 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
The first line contains an integer n ($1 \le n \le 10^6$) — the number of water tanks.

The second line contains n integers a1,a2,…,an ($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
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 ai does not exceed $10^{-9}$.

Formally, let your answer be a1,a2,…,an, and the jury's answer be b1,b2,…,bn. Your answer is accepted if and only if $\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$ for each i.

Examples
input
4
7 5 5 7
output
5.666666667
5.666666667
5.666666667
7.000000000
input
5
7 8 8 10 12
output
7.000000000
8.000000000
8.000000000
10.000000000
12.000000000
input
10
3 9 5 5 1 7 5 3 8 7
output
3.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
7.500000000
7.500000000
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.

## Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
{
ll   flag = 1, ans = 0;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
flag = 1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
ans = ans * 10 + c - '0';
c   = getchar();
}
return ans * flag;
}//cin的通过代码是2324 ms，我加了快读是1325 ms，scanf/printf是1248 ms
ll a[maxn], p[maxn], q[maxn];
int main()
{
ll n, x = 0, y = 0, pos = 0;
scanf("%lld",&n);
for (ll i = 1; i <= n; i++)
scanf("%lld",&a[i]);
for (ll i = 1; i <= n; i++)
{
x = a[i], y = 1;
while (pos && p[pos] * y >= x * q[pos])//p[pos] * y >= x * q[pos]这一句是用来计算新考虑的这个数对前面是否有影响，如果小于，说明加上这个数会使前面的数都减小，所以加上
x += p[pos], y += q[pos--];
p[++pos] = x, q[pos] = y;
}//计算出来总共pos组数，每组数有q[i]个
for (ll i = 1; i <= pos; i++)
for (ll j = 1; j <= q[i]; j++)
printf("%.9lf\n", p[i] * 1.0 / q[i]);
return 0;
}