Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high. 

<image>

A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strength of a group is the minimum height of the bear in that group.

Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.

Input

The first line of input contains integer n (1 ≤ n ≤ 2 × 105), the number of bears.

The second line contains n integers separated by space, a1, a2, ..., an (1 ≤ ai ≤ 109), heights of bears.

Output

Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.

Examples

Input

10
1 2 3 4 5 4 3 2 1 6


Output

6 4 4 3 3 2 2 1 1 1

Source: codeforces | Difficulty: HARD
Tags: Spanning trees

Sorting

Data structures

Dynamic programming


Solutions:
from sys import stdin, stdout

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

def print(x, end='\n'):
	stdout.write(str(x) + end)
(n, lst) = (int(input()), list(map(int, input().split())))
(nse, pse, stk, ans) = ([n for i in range(n)], [-1 for i in range(n)], [], [0 for i in range(n + 1)])
for i in range(n):
	while stk and lst[stk[-1]] > lst[i]:
		nse[stk.pop()] = i
	stk.append(i)
stk.clear()
for i in range(n - 1, -1, -1):
	while stk and lst[stk[-1]] > lst[i]:
		pse[stk.pop()] = i
	stk.append(i)
for i in range(n):
	ans[nse[i] - pse[i] - 1] = max(lst[i], ans[nse[i] - pse[i] - 1])
mnow = ans[n]
for i in range(n, -1, -1):
	mnow = max(mnow, ans[i])
	ans[i] = mnow
print(' '.join(map(str, ans[1:])))


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

def main_old(n, a):
	s = list(a)
	print(max(a), end=' ')
	for i in range(1, n):
		ns = list(s[:-1])
		mx = 0
		for j in range(len(ns)):
			ns[j] = min(s[j], s[j + 1])
			if ns[j] > mx:
				mx = ns[j]
		s = ns
		print(mx, end=' ')
from sys import stdout

def main(n, a):
	s = a
	buf = str(max(a))
	for i in range(n - 1, 0, -1):
		mx = 0
		for j in range(i):
			s[j] = min(s[j], s[j + 1])
			if s[j] > mx:
				mx = s[j]
		buf += ' ' + str(mx)
	stdout.write(buf + '\n')

def run(n, a):
	stack = []
	(l, r) = ([0] * n, [0] * n)
	for x in range(n):
		while len(stack) > 0 and a[stack[-1]] >= a[x]:
			stack.pop()
		if len(stack) == 0:
			l[x] = -1
		else:
			l[x] = stack[-1]
		stack.append(x)
	stack = []
	for x in range(n - 1, -1, -1):
		while len(stack) > 0 and a[stack[-1]] >= a[x]:
			stack.pop()
		if len(stack) == 0:
			r[x] = n
		else:
			r[x] = stack[-1]
		stack.append(x)
	sl = [-1] * n
	for x in range(n):
		v = r[x] - l[x] - 1
		sl[v - 1] = max(sl[v - 1], a[x])
	for x in range(n - 2, -1, -1):
		sl[x] = max(sl[x], sl[x + 1])
	print(' '.join([str(x) for x in sl]))

def main_input(info=0):
	n = int(input())
	a = VI()
	run(n, a)
main_input()


n = int(input())
l = [int(i) for i in input().split()]
stack = []
ans = [0] * n
left = [-1] * n
right = [n] * n
for i in range(n):
	while stack != [] and l[i] <= l[stack[-1]]:
		stack.pop()
	if stack != []:
		left[i] = stack[-1]
	stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
	while stack != [] and l[i] <= l[stack[-1]]:
		stack.pop()
	if stack != []:
		right[i] = stack[-1]
	stack.append(i)
for i in range(n):
	k = right[i] - left[i] - 1
	ans[k - 1] = max(ans[k - 1], l[i])
for i in range(n - 2, -1, -1):
	ans[i] = max(ans[i], ans[i + 1])
print(*ans)