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.

Difficulty: competition

Starter code:

Solutions:
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))


def main():
    from sys import stdin, stdout
    ans = []
    stdin.readline()
    for new_s in map(int, stdin.readline().split()):
        new_c = 1
        while ans and new_s * ans[-1][1] <= ans[-1][0] * new_c:
            old_s, old_c = ans.pop()
            new_s += old_s
            new_c += old_c
        ans.append((new_s, new_c))
    for s, c in ans:
        stdout.write(f'{s / c}\n' * c)


main()