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.*;
import java.util.*;
public class Feet {
  public static void main(String[] args) throws IOException {
	  
	  Scanner s=new Scanner(System.in);
	  
	  int n=s.nextInt();
	  int[] ans=new int[n];
	  int[] arr=new int[n];
	  int[] NSE=new int[n];
	  int[] PSE=new int[n];
	  
	  Stack<Integer> st=new Stack<>();
	  
	  for(int i=0; i<n; i++)
		  arr[i]=s.nextInt();
	  
	  for(int i=0; i<n; i++) {
		  
		  while(st.isEmpty()==false && arr[i]< arr[st.peek()])
			  NSE[st.pop()]=i;
		  
		  st.push(i);
	  }
	  
	  while(st.isEmpty()==false)
		  NSE[st.pop()]=n;
	  
	  
	  for(int i=n-1; i>=0; i--) {
		  
		  while(st.isEmpty()==false && arr[i]< arr[st.peek()])
			  PSE[st.pop()]=i;
		  
		  st.push(i);
	  }
	  
	  while(st.isEmpty()==false)
		  PSE[st.pop()]=-1;
	  
	  for(int i=0; i<n; i++) {
		  int act=NSE[i]-PSE[i]-2;
		  
		  if(arr[0]>ans[0])
		  ans[0]=arr[0];
		  if(arr[i]>ans[act])
		  ans[act]=arr[i];
	  }
	  
	  for(int j=n-2; j>=0; j--) {
		  if(ans[j] <= ans[j+1])
              ans[j] = ans[j+1];
	  }
	  
	  for(int k=0; k<n; k++)
		  System.out.print(ans[k]+" ");
  }
}

class Scanner 



{
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

	public String next() throws IOException 
	{
		while (st == null || !st.hasMoreTokens()) 
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}

	public int nextInt() throws IOException {return Integer.parseInt(next());}

	public long nextLong() throws IOException {return Long.parseLong(next());}

	public String nextLine() throws IOException {return br.readLine();}


	public double nextDouble() throws IOException
	{
		String x = next();
		StringBuilder sb = new StringBuilder("0");
		double res = 0, f = 1;
		boolean dec = false, neg = false;
		int start = 0;
		if(x.charAt(0) == '-')
		{
			neg = true;
			start++;
		}
		for(int i = start; i < x.length(); i++)
			if(x.charAt(i) == '.')
			{
				res = Long.parseLong(sb.toString());
				sb = new StringBuilder("0");
				dec = true;
			}
			else
			{
				sb.append(x.charAt(i));
				if(dec)
					f *= 10;
			}
		res += Long.parseLong(sb.toString()) / f;
		return res * (neg?-1:1);
	}

	public boolean ready() throws IOException {return br.ready();}



}