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-----
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-----
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$.
-----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.
n = int(input())
l = list(map(int, input().split()))

stack = []
for v in l:
    currVal = v
    currSize = 1
    div = v
    
    while stack:
        nex, nexS, nDiv = stack[-1]

        if div < nDiv:
            currSize += nexS
            currVal += nex
            stack.pop()

            div = currVal / currSize
        else:
            break
    stack.append((currVal, currSize, div))

out = []
for a, b, d in stack:
    thingy = str(d)
    for _ in range(b):
        out.append(thingy)
        
print('\n'.join(out))

n = int(input())
l = list(map(int, input().split()))

stack = []
for v in l:
    currVal = v
    currSize = 1
    div = v
    
    while stack:
        nex, nexS, nDiv = stack[-1]

        if div < nDiv:
            currSize += nexS
            currVal += nex
            stack.pop()

            div = currVal / currSize
        else:
            break
    stack.append((currVal, currSize, div))

out = []
for a, b, d in stack:
    thingy = str(d)
    for _ in range(b):
        out.append(thingy)
        
print('\n'.join(out))
