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: HARD
Tags: Geometry

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
n = int(input())
l = 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))


from __future__ import division, print_function
import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
l = list(map(int, input().split()))
su = [l[0]]
cou = [-1, 0]
for k in range(1, n):
	nd = 1
	ns = l[k]
	while len(cou) > 1 and su[-1] * (cou[-1] - cou[-2] + nd) > (su[-1] + ns) * (cou[-1] - cou[-2]):
		nd += cou[-1] - cou[-2]
		ns += su[-1]
		su.pop()
		cou.pop()
	cou.append(k)
	su.append(ns)
floats = []
for k in range(len(su)):
	floats += [su[k] / (cou[k + 1] - cou[k])] * (cou[k + 1] - cou[k])
if True:
	if False:
		print('\n'.join(map(str, floats)))
	if False:
		os.write(1, b'\n'.join((str(x).encode() for x in floats)))
	if False:
		os.write(1, b'\n'.join((b'%.9f' % x for x in floats)))
	if False:
		os.write(1, b'\n'.join((b'%d.%09d' % (x, (x - int(x)) * 1000000000.0 + 0.5) for x in floats)))
	if True:
		ans = bytearray()
		for x in floats:
			i = int(x)
			ans += b'%d.%09d\n' % (i, (x - i) * 1000000000.0 + 0.5)
		os.write(1, ans)
else:
	ans = bytearray()
	for k in range(len(su)):
		repeat = cou[k + 1] - cou[k]
		x = su[k] / repeat
		i = int(x)
		ans += b'%d.%09d\n' % (i, (x - i) * 1000000000.0 + 0.5) * repeat
	os.write(1, ans)


import sys
input = sys.stdin.buffer.readline

def main():
	n = int(input())
	a = list(map(int, input().split()))
	stack = []
	for i in a:
		nnew = 1
		while stack and stack[-1][0] >= i / nnew:
			(val, num) = stack.pop()
			i += val * num
			nnew += num
		stack.append((i / nnew, nnew))
	if len(stack) == n:
		print(*a, sep='\n')
		exit()
	for (val, num) in stack:
		opt = str(round(val, 9)) + '\n'
		sys.stdout.write(opt * num)
main()


N = int(input())
l = list(map(int, input().strip().split()))
q = [(0, 0)] * N
idx = 0
for x in reversed(l):
	xn = x
	xd = 1
	while idx:
		(n, d) = q[idx - 1]
		if xn * d < n * xd:
			break
		q[idx - 1] = (0, 0)
		xn += n
		xd += d
		idx -= 1
	q[idx] = (xn, xd)
	idx += 1
for (xn, xd) in reversed(q):
	if not xd:
		continue
	s = f'{xn / xd:.10f}'
	for _ in range(xd):
		print(s)


def main():
	import sys
	from collections import deque
	input = sys.stdin.buffer.readline
	N = int(input())
	A = list(map(int, input().split()))
	st = deque()
	st_append = st.append
	st_append((A[0], 1))
	for a in A[1:]:
		L = 1
		while st[-1][0] >= a:
			(b, n) = st.pop()
			a = (a * L + b * n) / (n + L)
			L += n
			if len(st) == 0:
				break
		st_append((a, L))
	while st:
		(b, n) = st.popleft()
		print((str(b) + '\n') * n, end='')
main()


n = int(input())
xs = list(map(int, input().split()))
ans = []
for (i, x) in enumerate(xs):
	summ = x
	cnt = 1
	for (s, c) in reversed(ans):
		if (summ + s) * c > s * (cnt + c):
			break
		cnt += c
		summ += s
		ans.pop()
	ans.append((summ, cnt))
for (summ, cnt) in ans:
	m = str(summ / cnt)
	print('\n'.join((m for _ in range(cnt))))


from sys import stdin, gettrace, stdout

def main():
	n = int(input())
	aa = [int(a) for a in input().split()]
	sum = [0]
	for a in aa:
		sum.append(sum[-1] + a)

	def mean(i, j):
		return (sum[j] - sum[i]) / (j - i)
	stk = []
	for i in range(n):
		stk.append((i, i + 1))
		while len(stk) > 1 and mean(*stk[-2]) >= mean(*stk[-1]):
			(_, j) = stk.pop()
			(i, _) = stk.pop()
			stk.append((i, j))
	for (i, j) in stk:
		v = str(mean(i, j)) + '\n'
		for k in range(j - i):
			stdout.write(v)
main()
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')


n = int(input())
a = list(map(int, input().split()))
w = [(a[0], 1)]
for i in range(1, n):
	(x, y) = (a[i], 1)
	while w and w[-1][0] * y >= w[-1][1] * x:
		(dx, dy) = w.pop()
		(x, y) = (x + dx, y + dy)
	w.append((x, y))
print(''.join([(str(x / y) + '\n') * y for (x, y) in w]))


from math import factorial
from collections import Counter
from heapq import heapify, heappop, heappush
from sys import stdin

def RL():
	return map(int, stdin.readline().rstrip().split())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 1000000007
INF = float('inf')

def main():
	n = int(input())
	arr = [int(i) for i in input().split()]
	sm = [0.0]
	for i in arr:
		sm.append(sm[-1] + i)

	def mean(t):
		(i, j) = t
		return (sm[j] - sm[i]) / (j - i)
	stack = []
	for i in range(n):
		stack.append((i, i + 1))
		while len(stack) > 1 and mean(stack[-2]) >= mean(stack[-1]):
			(a, b) = stack.pop()
			(c, d) = stack.pop()
			stack.append((c, b))
	res = [0.0] * n
	for (n, v) in stack:
		m = mean((n, v))
		for i in range(n, v):
			res[i] = m
	print(*res)
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
N = INT()
A = LIST()
stack = []
for (i, a) in enumerate(A):
	stack.append((a, 1))
	while len(stack) >= 2 and stack[-2][0] > stack[-1][0]:
		(a1, cnt1) = stack.pop()
		(a2, cnt2) = stack.pop()
		merged = (a1 * cnt1 + a2 * cnt2) / (cnt1 + cnt2)
		stack.append((merged, cnt1 + cnt2))
for (a, cnt) in stack:
	print((str(a) + '\n') * cnt, end='')


import sys, os
n = int(sys.stdin.buffer.readline())
A = [int(x) for x in sys.stdin.buffer.readline().split()]
cumsum = [0.0]
for a in A:
	cumsum.append(cumsum[-1] + a)

def mean(interval):
	(i, j) = interval
	return (cumsum[j] - cumsum[i]) / (j - i)
B = []
for i in range(n):
	B.append((i, i + 1))
	while len(B) > 1 and mean(B[-2]) >= mean(B[-1]):
		(_, j) = B.pop()
		(i, _) = B.pop()
		B.append((i, j))
ans = [0.0] * n
for (i, j) in B:
	x = mean((i, j))
	for k in range(i, j):
		ans[k] = x
os.write(1, b' '.join((repr(x).encode('ascii') for x in ans)))


import sys, math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())
t = 1
for tt in range(t):
	n = inp()
	a = inlt()
	a = [(a[i], 1) for i in range(len(a))]
	qw = []
	for i in a:
		while len(qw) >= 1 and qw[-1][0] / qw[-1][1] > i[0] / i[1]:
			(q, w) = qw.pop()
			i = (i[0] + q, i[1] + w)
		qw.append(i)
	for i in range(len(qw)):
		sys.stdout.write((str(qw[i][0] / qw[i][1]) + '\n') * qw[i][1])


from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
q_num = deque()
q_len = deque()
for i in range(n):
	num_0 = a[i]
	len_0 = 1
	while True:
		if len(q_num) == 0:
			q_num.append(num_0)
			q_len.append(len_0)
			break
		(num_1, len_1) = (q_num[-1], q_len[-1])
		len_new = len_1 + len_0
		num_new = (num_1 * len_1 + num_0 * len_0) / len_new
		if num_0 < num_new:
			q_num.pop()
			q_len.pop()
			num_0 = num_new
			len_0 = len_new
		else:
			q_num.append(num_0)
			q_len.append(len_0)
			break
while q_len:
	num_0 = q_num.popleft()
	len_0 = q_len.popleft()
	print((str(num_0) + '\n') * len_0, end='')


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
stk = []
for i in a:
	now_sum = i
	now_cnt = 1
	while stk and now_sum * stk[-1][1] < stk[-1][0] * now_cnt:
		(temp_sum, temp_cnt) = stk.pop()
		now_sum += temp_sum
		now_cnt += temp_cnt
	stk.append((now_sum, now_cnt))
for i in stk:
	temp_ans = str(i[0] / i[1])
	for j in range(i[1]):
		print(temp_ans)


def main():
	from sys import stdin, stdout
	ans = []
	stdin.readline()
	for ai in map(int, map(int, stdin.readline().split())):
		cnt = 1
		while ans and ai * ans[-1][0] <= ans[-1][1] * cnt:
			(c, r) = ans.pop()
			ai += r
			cnt += c
		ans.append((cnt, ai))
	for (i, res) in ans:
		m = str(res / i)
		stdout.write((m + '\n') * i)
main()


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()


import sys, math
import io, os
data = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write('\n'.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(var)
from decimal import Decimal
mod = 10 ** 9 + 7
INF = float('inf')
n = int(data())
avg = []
for i in mdata():
	s = i
	l = 1
	while avg and avg[-1][0] * l > s * avg[-1][1]:
		(x, y) = avg.pop()
		s += x
		l += y
	avg.append((s, l))
ans = []
for (s, l) in avg:
	avg1 = s / l
	for i in range(l):
		ans.append(avg1)
os.write(1, b' '.join((repr(x).encode('ascii') for x in ans)))


import sys
input = sys.stdin.readline
n = int(input())
A = tuple(map(int, input().split()))
W = []
for a in A:
	W.append((a, 1))
	while len(W) >= 2 and W[-2][0] * W[-1][1] > W[-1][0] * W[-2][1]:
		(x, y) = W.pop()
		(z, w) = W.pop()
		W.append((x + z, y + w))
for (x, y) in W:
	sys.stdout.write((str(x / y) + '\n') * y)


from operator import itemgetter
from collections import Counter
from collections import deque
import sys
input = sys.stdin.readline

def solve(a):
	b = [-1]
	c = [1]
	for aa in a:
		b.append(aa)
		c.append(1)
		while b[-2] * c[-1] >= b[-1] * c[-2]:
			a1 = b.pop()
			i1 = c.pop()
			b[-1] = a1 + b[-1]
			c[-1] = i1 + c[-1]
	for (i, aa) in enumerate(b[1:]):
		cc = c[i + 1]
		d = aa / cc
		ss = (str(d) + '\n') * cc
		sys.stdout.write(ss)

def main():
	n = int(input())
	a = list(map(int, input().split()))
	solve(a)
main()


def main():
	n = int(input())
	a = list(map(int, input().split()))
	ans = []
	for (i, ai) in enumerate(a):
		res = ai
		cnt = 1
		for (c, s) in reversed(ans):
			if (res + s) * c > s * (c + cnt):
				break
			res += s
			cnt += c
			ans.pop()
		ans.append((cnt, res))
	for (i, res) in ans:
		m = str(res / i)
		print('\n'.join((m for _ in range(i))))
main()


n = int(input())
a = list(map(int, input().split()))
c = []
for el in a:
	c.append((el, 1))
	while len(c) > 1 and c[-1][0] * c[-2][1] < c[-2][0] * c[-1][1]:
		c[-2] = (c[-2][0] + c[-1][0], c[-2][1] + c[-1][1])
		c.pop()
ans = []
for el in c:
	ans.extend([str(el[0] / el[1])] * el[1])
print('\n'.join(ans))


import os, io
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
sums = [0]
curr = 0
t = []
for i in range(n):
	curr += a[i]
	sums.append(curr)
for i in range(n):
	t.append([i - 1, i])
for i in range(1, n):
	while t[i][0] != -1 and (sums[t[i][1] + 1] - sums[t[i][0] + 1]) * (t[i][0] - t[t[i][0]][0]) < (sums[t[i][0] + 1] - sums[t[t[i][0]][0] + 1]) * (t[i][1] - t[i][0]):
		t[i][0] = t[t[i][0]][0]
i = n - 1
ans = []
while i >= 0:
	k = str((sums[t[i][1] + 1] - sums[t[i][0] + 1]) / (t[i][1] - t[i][0]))
	for j in range(t[i][1] - t[i][0]):
		ans.append(k)
	i -= t[i][1] - t[i][0]
ans.reverse()
print(' '.join(ans))


def main():
	n = int(input().strip())
	A = [int(s) for s in input().strip().split()]
	stack = []
	for a in A:
		k = 1
		while stack and stack[-1][0] * k > a * stack[-1][1]:
			(b, m) = stack.pop()
			a += b
			k += m
		stack.append((a, k))
	for (b, m) in stack:
		avg = f'{b / m:.10f}'
		for _ in range(m):
			print(avg)
main()


def ConvexHull(Points):
	Qs = []
	for (x, y) in Points:
		while len(Qs) > 1:
			(x1, y1) = Qs[-1]
			(x2, y2) = Qs[-2]
			if (y1 - y) * (x - x2) > (y - y2) * (x1 - x):
				Qs.pop()
			else:
				break
		Qs.append((x, y))
	return Qs
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
Points = [(0, 0)]
tmp = 0
for (i, a) in enumerate(A):
	tmp += a
	Points.append((i + 1, tmp))
C = ConvexHull(Points)
ans = []
for i in range(len(C) - 1):
	count = C[i + 1][0] - C[i][0]
	value = C[i + 1][1] - C[i][1]
	print((str(value / count) + '\n') * count, end='')


from sys import stdin, stdout
q = int(stdin.readline())
tanks = [int(x) for x in stdin.readline().split()]
avgs = []
c = -1
for x in range(q):
	sum1 = tanks[x]
	i = 1
	while c >= 0 and sum1 * avgs[c][1] <= i * avgs[c][0]:
		sum1 += avgs[c][0]
		i += avgs[c][1]
		c -= 1
	c += 1
	if c < len(avgs):
		avgs[c] = [sum1, i]
	else:
		avgs.append([sum1, i])
count = 0
for (a, b) in avgs:
	stdout.write((str(a / b) + '\n') * b)
	count += b
	if count >= q:
		break


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
stack = []
for aa in a:
	stack.append([aa, 1])
	while len(stack) > 1 and stack[-1][0] / stack[-1][1] < stack[-2][0] / stack[-2][1]:
		stack[-2] = [stack[-2][0] + stack[-1][0], stack[-2][1] + stack[-1][1]]
		stack.pop()
b = []
for (block, l) in stack:
	b.extend([str(block / l)] * l)
print('\n'.join(b))


import sys
input = sys.stdin.readline
n = int(input())
W = []
for a in map(int, input().split()):
	ln = a
	lc = 1
	while W and W[-1][0] * lc > ln * W[-1][1]:
		(x, y) = W.pop()
		(ln, lc) = (ln + x, lc + y)
	W.append((ln, lc))
for (x, y) in W:
	sys.stdout.write((str(x / y) + '\n') * y)


def main():
	(n, *a) = map(int, open(0).read().split())
	d = n + 1
	b = [a[0] * d + 1]
	for i in range(1, n):
		if b[-1] // d == a[i]:
			b[-1] += 1
		else:
			b.append(a[i] * d + 1)
	(bx, bi) = divmod(b[0], d)
	bx *= bi
	s = [bx * d + bi]
	for ii in range(1, len(b)):
		(cx, ci) = divmod(b[ii], d)
		cx *= ci
		s.append(cx * d + ci)
		(bx, bi) = divmod(s[-2], d)
		(cx, ci) = divmod(s[-1], d)
		while cx * bi < bx * ci:
			s.pop()
			s[-1] = (bx + cx) * d + bi + ci
			if len(s) == 1:
				break
			(bx, bi) = divmod(s[-2], d)
			(cx, ci) = divmod(s[-1], d)
	ans = []
	for ii in range(len(s)):
		(sx, si) = divmod(s[ii], d)
		ans += [str(sx / si)] * si
	print(' '.join(ans))
main()


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, A):
	for i in range(N):
		best = (A[i], i, i + 1)
		for j in range(i + 1, N + 1):
			avg = sum(A[i:j]) / (j - i)
			best = min(best, (avg, i, j))
		if best[0] < A[i]:
			(avg, i, j) = best
			A[i:j] = [avg] * (j - i)
	return '\n'.join(map(str, A))

def solve(N, A):
	blocks = [(0, 0)]

	def combine(block1, block2):
		(h1, w1) = block1
		(h2, w2) = block2
		total = h1 * w1 + h2 * w2
		w = w1 + w2
		return (total / w, w)
	for x in A:
		block = (x, 1)
		while True:
			combinedBlock = combine(blocks[-1], block)
			if combinedBlock[0] <= blocks[-1][0]:
				blocks.pop()
				block = combinedBlock
			else:
				blocks.append(block)
				break
	ans = []
	for (h, w) in blocks:
		val = str(h)
		ans.extend([val] * w)
	return '\n'.join(ans)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = solve(N, A)
print(ans)


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
stack = []
L = [1] * N
for i in range(N):
	while stack and A[stack[-1]] * L[i] >= A[i] * L[stack[-1]]:
		j = stack.pop()
		L[j] += L[i]
		A[j] += A[i]
		i = j
	stack.append(i)
for i in stack:
	sys.stdout.write((str(A[i] / L[i]) + '\n') * L[i])


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = list(map(int, input().split()))
	le = [1 for i in range(n + 1)]
	sum = [0 for i in range(n + 1)]
	tmp = 1
	for i in range(n):
		sum[tmp] = 1.0 * a[i]
		le[tmp] = 1
		while tmp > 1 and sum[tmp] < sum[tmp - 1]:
			sum[tmp - 1] = (sum[tmp] * le[tmp] + sum[tmp - 1] * le[tmp - 1]) / (le[tmp] + le[tmp - 1])
			le[tmp - 1] += le[tmp]
			tmp -= 1
		tmp += 1
	ans = ''
	for i in range(1, tmp):
		for j in range(le[i]):
			print(sum[i], end=' ')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
f = [1] * n
p = [-1] * n
for i in range(0, n - 1):
	p[i] = i + 1
i = n - 2
j = n - 1
while i >= 0:
	if a[i] * f[j] >= a[j] * f[i]:
		(a[i], f[i], f[j], p[i]) = (a[j] + a[i], f[j] + f[i], 0, p[j])
		if p[i] != -1:
			j = p[i]
		else:
			p[j] = i
			(i, j) = (i - 1, i)
	else:
		(i, j) = (i - 1, i)
ans = [0] * n
k = 0
for i in range(0, n):
	if f[i] != 0:
		c = str(a[i] / f[i])
	for j in range(0, f[i]):
		ans[k] = c
		k = k + 1
print('\n'.join(ans))


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List

def solve(N, A):
	W = []
	for v in A:
		W.append((v, 1))
		while len(W) >= 2 and W[-2][0] * W[-1][1] > W[-1][0] * W[-2][1]:
			(a, b) = W.pop()
			(c, d) = W.pop()
			W.append((a + c, b + d))
	for (x, y) in W:
		sys.stdout.write((str(x / y) + '\n') * y)
	sys.stdout.flush()
N = int(input())
A = [int(x) for x in input().split()]
solve(N, A)


from sys import stdin, gettrace, stdout
if not gettrace():

	def input():
		return next(stdin)[:-1]

def main():
	n = int(input())
	aa = [int(a) for a in input().split()]
	sum = [0]
	for a in aa:
		sum.append(sum[-1] + a)

	def mean(i, j):
		return (sum[j] - sum[i]) / (j - i)
	stk = []
	for i in range(n):
		stk.append((i, i + 1))
		while len(stk) > 1 and mean(*stk[-2]) >= mean(*stk[-1]):
			(_, j) = stk.pop()
			(i, _) = stk.pop()
			stk.append((i, j))
	for (i, j) in stk:
		v = str(mean(i, j)) + '\n'
		for k in range(j - i):
			stdout.write(v)
main()


def solution():
	from collections import deque
	from sys import stdin, stdout
	(_int, _input, _print, _str, _range) = (int, stdin.readline, stdout.write, str, range)
	n = _int(_input())
	l = [_int(x) for x in _input().split()]
	current = l[0]
	count = 1
	ans = deque()
	ans_count = 0
	_add = ans.append
	_pop = ans.pop
	for i in _range(1, n):
		if current >= l[i] * count:
			current += l[i]
			count += 1
		else:
			while ans_count and current * ans[-1][1] <= ans[-1][0] * count:
				(x, y) = _pop()
				ans_count -= 1
				current += x
				count += y
			_add((current, count))
			ans_count += 1
			current = l[i]
			count = 1
	while ans_count and current * ans[-1][1] <= ans[-1][0] * count:
		(x, y) = _pop()
		ans_count -= 1
		current += x
		count += y
	_add((current, count))
	_print(''.join([(_str(x / y) + '\n') * y for (x, y) in ans]))
solution()


import os, io
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = n + 1
	b = [a[0] * d + 1]
	for i in range(1, n):
		if b[-1] // d == a[i]:
			b[-1] += 1
		else:
			b.append(a[i] * d + 1)
	(bx, bi) = divmod(b[0], d)
	bx *= bi
	s = [bx * d + bi]
	for ii in range(1, len(b)):
		(cx, ci) = divmod(b[ii], d)
		cx *= ci
		s.append(cx * d + ci)
		(bx, bi) = divmod(s[-2], d)
		(cx, ci) = divmod(s[-1], d)
		while cx * bi < bx * ci:
			s.pop()
			s[-1] = (bx + cx) * d + bi + ci
			if len(s) == 1:
				break
			(bx, bi) = divmod(s[-2], d)
			(cx, ci) = divmod(s[-1], d)
	ans = []
	for ii in range(len(s)):
		(sx, si) = divmod(s[ii], d)
		ans += [str(sx / si)] * si
	print(' '.join(ans))
main()


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, A):
	for i in range(N):
		best = (A[i], i, i + 1)
		for j in range(i + 1, N + 1):
			avg = sum(A[i:j]) / (j - i)
			best = min(best, (avg, i, j))
		if best[0] < A[i]:
			(avg, i, j) = best
			A[i:j] = [avg] * (j - i)
	return '\n'.join(map(str, A))

def solve(N, A):
	pref = [0]
	for x in A:
		pref.append(pref[-1] + x)
	i = 0
	while i < N:
		best = (A[i], i, i + 1)
		for j in range(i + 1, N + 1):
			avg = (pref[j] - pref[i]) / (j - i)
			best = min(best, (avg, i, j))
		if best[0] < A[i]:
			(avg, i, j) = best
			A[i:j] = [avg] * (j - i)
			i = j
		else:
			i += 1
	return '\n'.join(map(str, A))

def solve(N, A):
	heights = [(0, 0)]

	def combine(hw1, hw2):
		(h1, w1) = hw1
		(h2, w2) = hw2
		total = h1 * w1 + h2 * w2
		w = w1 + w2
		return (total / w, w)
	cost = 0
	for x in A:
		hw = (x, 1)
		while True:
			c = combine(heights[-1], hw)
			if c[0] <= heights[-1][0]:
				heights.pop()
				hw = c
			else:
				heights.append(hw)
				cost += 1
				break
	assert cost == N
	ans = []
	for (h, w) in heights:
		ans.extend([str(h)] * w)
	return '\n'.join(ans)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = solve(N, A)
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()

def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = n + 1
	b = [a[0] * d + 1]
	for i in range(1, n):
		if b[-1] // d == a[i]:
			b[-1] += 1
		else:
			b.append(a[i] * d + 1)
	(bx, bi) = divmod(b[0], d)
	bx *= bi
	s = [bx * d + bi]
	for ii in range(1, len(b)):
		(cx, ci) = divmod(b[ii], d)
		cx *= ci
		s.append(cx * d + ci)
		(bx, bi) = divmod(s[-2], d)
		(cx, ci) = divmod(s[-1], d)
		while cx * bi < bx * ci:
			s.pop()
			s[-1] = (bx + cx) * d + bi + ci
			if len(s) == 1:
				break
			(bx, bi) = divmod(s[-2], d)
			(cx, ci) = divmod(s[-1], d)
	ans = []
	for ii in range(len(s)):
		(sx, si) = divmod(s[ii], d)
		ans += [str(sx / si)] * si
	print(' '.join(ans))
main()