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 
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x548D
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         int[] right = new int[N];
         Arrays.fill(right, N);
         Stack<Integer> stack = new Stack<Integer>();
         for(int i=0; i < N; i++)
         {
            while(stack.size() > 0 && arr[stack.peek()] > arr[i])
               right[stack.pop()] = i;
            stack.push(i);
         }
         int[] left = new int[N];
         Arrays.fill(left, -1);
         stack = new Stack<Integer>();
         for(int i=N-1; i >= 0; i--)
         {
            while(stack.size() > 0 && arr[stack.peek()] > arr[i])
               left[stack.pop()] = i;
            stack.push(i);
         }
         ArrayList<Range> ls = new ArrayList<Range>();
         for(int i=0; i < N; i++)
            ls.add(new Range(right[i]-left[i]-1, arr[i]));
         Collections.sort(ls);
         int[] res = new int[N+1];
         for(Range r: ls)
            res[r.len] = Math.max(res[r.len], r.val);
         for(int i=N-1; i >= 1; i--)
            if(res[i] <= res[i+1])
               res[i] = res[i+1];
         for(int i=1; i <= N; i++)
            sb.append(res[i]+" ");
         System.out.println(sb);
      }
   }
   class Range implements Comparable<Range>
   {
      public int len;
      public int val;
      
      public Range(int a, int b)
      {
         len = a;
         val = b;
      }
      public int compareTo(Range oth)
      {
         if(len == oth.len)
            return val-oth.val;
         return len-oth.len;
      }
   }