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 
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.SortedSet;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main
{	
	/********************************************** a list of common variables **********************************************/
	
	private MyScanner scan = new MyScanner();
	private PrintWriter out = new PrintWriter(System.out);
	private final double PI = Math.acos(-1.0);
	private final int SIZEN = (int)(1e7);
	private final int MOD = (int)(1e9 + 7);
	
	public void foo()
	{
		int n = scan.nextInt();
		int[] a = new int[n];
		for(int i = 0;i < n;++i)
		{
			a[i] = scan.nextInt();
		}
		int[] left = new int[n];
		int[] right = new int[n];
		Stack<int[]> s = new Stack<int[]>();
		s.push(new int[]{-1, -1}); //p[0]:num, p[1]:index
		for(int i = 0;i < n;++i)
		{
			while(!s.isEmpty())
			{
				int[] p = s.peek();
				if(a[i] >= p[0])
				{
					left[i] = a[i] > p[0] ? p[1] + 1 : left[p[1]];
					break;
				}
				else
				{
					right[p[1]] = i - 1;
					s.pop();
				}
			}
			s.push(new int[]{a[i], i});	
		}
		while(s.size() > 1)
		{
			int[] p = s.pop();
			right[p[1]] = n - 1;
		}
		int[] ans = new int[n + 1];
		for(int i = 0;i < n;++i)
		{
			int d = right[i] - left[i] + 1;
			ans[d] = Math.max(ans[d], a[i]);
		}
		for(int i = n - 1;i >= 1;--i)
		{
			ans[i] = Math.max(ans[i], ans[i + 1]);
		}
		for(int i = 1;i <= n;++i)
		{
			out.print(ans[i] + " ");
		}
	}

	public static void main(String[] args)
	{
		Main m = new Main();
		m.foo();
		m.out.close();
	}

	/********************************************** a list of common algorithms **********************************************/
	
	/**
	 * KMP match, i.e. kmpMatch("abcd", "bcd") = 1, kmpMatch("abcd", "bfcd") = -1.
	 * 
	 * @param t: String to match.
	 * @param p: String to be matched.
	 * @return if can match, first index; otherwise -1.
	 */
	public int kmpMatch(char[] t, char[] p)
	{
		int n = t.length;
		int m = p.length;
		int[] next = new int[m + 1];
		next[0] = -1;
		int j = -1;
		for(int i = 1;i < m;++i)
		{
			while(j >= 0 && p[i] != p[j + 1])
			{
				j = next[j];
			}
			if(p[i] == p[j + 1])
			{
				++j;
			}
			next[i] = j;
		}
		j = -1;
		for(int i = 0;i < n;++i)
		{
			while(j >= 0 && t[i] != p[j + 1])
			{
				j = next[j];
			}
			if(t[i] == p[j + 1])
			{
				++j;
			}
			if(j == m - 1)
			{
				return i - m + 1;
			}
		}
		return -1;
	}

	class MyScanner
	{
	    private byte[] buf = new byte[1024];
	    private int curChar;
	    private int numChars;
	    BufferedInputStream bis = new BufferedInputStream(System.in);

	    public int read() 
	    {
	        if (-1 == numChars)
	        {
	        	throw new InputMismatchException();
	        }
	        if (curChar >= numChars)
	        {
	            curChar = 0;
	            try 
	            {
	                numChars = bis.read(buf);
	            }
	            catch (IOException e)
	            {
	                throw new InputMismatchException();
	            }
	            if (numChars <= 0)
	            {
	            	return -1;
	            }
	        }
	        return buf[curChar++];
	    }

	    public int nextInt() 
	    {
	        int c = read();
	        while (isSpaceChar(c))
	        {
	        	c = read();
	        }
	        int sgn = 1;
	        if (c == '-') 
	        {
	            sgn = -1;
	            c = read();
	        }
	        int res = 0;
	        do 
	        {
	            if (c < '0' || c > '9')
	            {
	            	throw new InputMismatchException();
	            }
	            res *= 10;
	            res += c - '0';
	            c = read();
	        } while (!isSpaceChar(c));
	        return res * sgn;
	    }
	    
	    public long nextLong() 
	    {
	    	int c = read();
	    	while (isSpaceChar(c))
	    	{
	    		c = read();
	    	}
	    	int sgn = 1;
	    	if (c == '-') 
	    	{
	    		sgn = -1;
	    		c = read();
	    	}
	    	long res = 0;
	    	do 
	    	{
	    		if (c < '0' || c > '9')
	    		{
	    			throw new InputMismatchException();
	    		}
	    		res *= 10;
	    		res += c - '0';
	    		c = read();
	    	} while (!isSpaceChar(c));
	    	return res * sgn;
	    }
	    
	    public double nextDouble() 
	    {
	        int c = read();
	        while (isSpaceChar(c))
	        {
	        	c = read();
	        }
	        int sgn = 1;
	        if (c == '-')
	        {
	            sgn = -1;
	            c = read();
	        }
	        double res = 0;
	        while (!isSpaceChar(c) && c != '.') 
	        {
	            if (c == 'e' || c == 'E')
	            {
	            	return res * Math.pow(10, nextInt());
	            }
	            if (c < '0' || c > '9')
	            {
	            	throw new InputMismatchException();
	            }
	            res *= 10;
	            res += c & 15;
	            c = read();
	        }
	        if (c == '.') 
	        {
	            c = read();
	            double m = 1;
	            while (!isSpaceChar(c)) 
	            {
	                if (c == 'e' || c == 'E')
	                {
	                	return res * Math.pow(10, nextInt());
	                }
	                if (c < '0' || c > '9')
	                {
	                	throw new InputMismatchException();
	                }
	                m /= 10;
	                res += (c & 15) * m;
	                c = read();
	            }
	        }
	        return res * sgn;
	    }
	    
	    public String next()
	    {
	        int c = read();
	        while (isSpaceChar(c))
	        {
	        	c = read();
	        }
	        StringBuilder res = new StringBuilder();
	        do 
	        {
	            res.appendCodePoint(c);
	            c = read();
	        } while (!isSpaceChar(c));
	        return res.toString();
	    }

	    private boolean isSpaceChar(int c) 
	    {
	        return ' ' == c || '\n' == c || '\r' == c || '\t' == c || -1 == c;
	    }
	}
}