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≤ l ≤ r ≤ n), and redistribute water in tanks l, l+1, ..., r evenly. In other words, replace each of a_l, a_{l+1}, ..., a_r by \frac{a_l + a_{l+1} + ... + 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 ≤ n ≤ 10^6) — the number of water tanks.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 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, ..., a_n, and the jury's answer be b_1, b_2, ..., b_n. Your answer is accepted if and only if \frac{|a_i - b_i|}{max{(1, |b_i|)}} ≤ 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:
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()


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))
ans = []
for (a, cnt) in stack:
	ans += [str(a)] * cnt
print('\n'.join(ans))


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


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


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


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


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 main():
	import sys
	input = sys.stdin.readline
	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()


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)


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


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


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


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


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