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.util.*;
import java.io.*;
import static java.lang.Math.*;
public class B
{
    static InputReader in=new InputReader(System.in);
    static OutputWriter out=new OutputWriter(System.out);
    static StringBuilder sb=new StringBuilder();
    static long MOD = (long)(1e9+7);
    static long IM2 = (long)(500000004L);
    // Main Class Starts Here

    public static void main(String args[])throws IOException
    {
        // Write your code.
        int t=1;
        while(t-->0){
            int n = in();
            int a[] = an(n);
            Stack<Integer> st = new Stack<Integer>();
            int r[] = new int[n];
            int l[] = new int[n];
            st.push(0);
            for(int i=1;i<n;i++){
                if(a[i] >= a[i-1]){
                    st.push(i);
                }
                else{
                    while(!st.isEmpty() && a[st.peek()] > a[i]){
                        int index = st.pop();
                        r[index] = i - index;
                    }
                    st.push(i);
                }
            }
            while(!st.isEmpty()){
                int index = st.pop();
                r[index] =  n  - index;
            }
            // prln(Arrays.toString(r));

            // now calculate for left.

            st.clear();

            st.push(n-1);
            for(int i=n-2;i>=0;i--){
                if(a[i] >= a[i+1]){
                    st.push(i);
                }
                else{
                    while(!st.isEmpty() && a[st.peek()] > a[i]){
                        int index = st.pop();
                        l[index] = index - i;
                    }
                    st.push(i);
                }
            }
            while(!st.isEmpty()){
                int index = st.pop();
                l[index] =  index + 1;
            }
            // prln(Arrays.toString(l));
            int sum[] = new int[n];
            for(int i=0;i<n;i++) sum[i] = r[i] + l[i] - 1;
            HashMap<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<n;i++){
                int get = map.getOrDefault(sum[i], -1);
                if(get == -1) map.put(sum[i], a[i]);
                else{
                    map.put(sum[i], max(a[i],get));
                }
            }

            // prln(Arrays.toString(sum));

            // prln(map);

            int ans[] = new int[n+1];
            Arrays.fill(ans, -1);
            for(int i=1;i<=n;i++){
                int get = map.getOrDefault(i,-1);
                ans[i] = max(ans[i], get);
            }
            for(int i = n-1 ;i >= 1;i--){
                ans[i] = max(ans[i], ans[i+1]);
            }
            // prln(Arrays.toString(ans));

            for(int i = 1;i <= n;i++) app(ans[i]+" ");
         }
        out.printLine(sb);
        out.close();
    }

    public static class Trio
    {
        int index;
        int value;
        int freq;

        public Trio(int index,int value,int freq){
            this.index = index;
            this.value = value;
            this.freq = freq;
        }

    }

    public static int lis(int a[]) {
        int n=a.length;
        if(n==0 || n==1)
            return n;
        int dp[] = new int[n];
        for(int i=0;i<n;i++) {
            dp[i] = 1;
            for(int j=0;j<i;j++) {
                if(a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], (dp[j]+1));
                }
            }
        }
        Arrays.sort(dp);
        return dp[n-1];
    }

    public static long rev(long n) {
        if(n<10L)
            return n;
        long rev = 0L;
        while(n != 0L) {
            long a = n % 10L;
            rev = a + rev*10L;
            n /= 10L;
        }
        return rev;
    }

    public static long pow(long a,long b) {
        if(b==0)
            return 1L;
        if(b==1)
            return a % MOD;
        long f = a * a;
        if(f > MOD)
            f %= MOD;
        long val = pow(f, b/2) % MOD;
        if(b % 2 == 0)
            return val;
        else {
            long temp = val * (a % MOD);
            if(temp > MOD)
                temp = temp % MOD;
            return temp;
        }
    }

    public static long lcm(long a,long b) {
        long lcm = (a*b)/gcd(a,b);
        return lcm;
    }

    public static long gcd(long a,long b) {
        if(b==0)
            return a;
        return gcd(b, a%b);
    }

    public static int[] an(int n) {
        int ar[]=new int[n];
        for(int i=0;i<n;i++)
            ar[i]=in();
        return ar;
    }

    public static long[] lan(int n) {
        long ar[]=new long[n];
        for(int i=0;i<n;i++)
            ar[i]=lin();
        return ar;
    }

    public static String atos(Object ar[]) {
        return Arrays.toString(ar);
    }

    public static int in() {
        return in.readInt();
    }

    public static long lin() {
        return in.readLong();
    }

    public static String sn() {
        return in.readString();
    }

    public static void prln(Object o) {
        out.printLine(o);
    }

    public static void prn(Object o) {
        out.print(o);
    }

    public static int getMax(int a[]) {
        int n = a.length;
        int max = a[0];
        for(int i=1; i < n; i++) {
            max = Math.max(max, a[i]);
        }
        return max;
    }

    public static int getMin(int a[]) {
        int n = a.length;
        int min = a[0];
        for(int i=1; i < n; i++) {
            min = Math.min(min, a[i]);
        }
        return min;
    }

    public static void display(int a[]) {
        out.printLine(Arrays.toString(a));
    }

    public static HashMap<Integer,Integer> hm(int a[]){
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0; i < a.length;i++) {
            int keep = (int)map.getOrDefault(a[i],0);
            map.put(a[i],++keep);
        }
        return map;
    }

    public static void app(Object o) {
        sb.append(o);
    }

    public static long calcManhattanDist(int x1,int y1,int x2,int y2) {
        long xa = Math.abs(x1-x2);
        long ya = Math.abs(y1-y2);
        return (xa+ya);
    }


    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

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

        public int readInt() {
            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 readLong() {
            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 String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object...objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object...objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }
    }
}