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.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class D {

    private static class Solution implements Runnable {

        private static final long modulo = 1000000007;


        private void solve() {
            int n = in.nextInt();

            int[] a = new int[n];
            int[] l = new int[n];
            int[] r = new int[n];
            int[] ans = new int[n + 1];


            Arrays.fill(l, -1);
            Arrays.fill(r, n);

            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }

            ArrayDeque<Integer> s = new ArrayDeque<>();

            for (int i = 0; i < n; i++) {
                while (!s.isEmpty() && a[s.peek()] >= a[i]) {
                    s.pop();
                }
                if (!s.isEmpty()) {
                    l[i] = s.peek();
                }
                s.push(i);
            }

            s.clear();
            for (int i = n - 1; i >= 0; i--) {
                while (!s.isEmpty() && a[s.peek()] >= a[i]) {
                    s.pop();
                }
                if (!s.isEmpty()) {
                    r[i] = s.peek();
                }
                s.push(i);
            }

            for (int i = 0; i < n; i++) {
                int len = r[i] - l[i] - 1;
                ans[len] = Math.max(ans[len], a[i]);
            }

            for (int i = n - 1; i >= 0; i--) {
                ans[i] = Math.max(ans[i], ans[i + 1]);
            }

            for (int i = 1; i < n + 1; i++) {
                out.print(ans[i] + " ");
            }
        }

        private long inverse(long a) {
            long result = 1;
            int n = (int) modulo - 2;
            while (n != 0) {
                if ((n & 1) == 1)
                    result = (result * a) % modulo;
                a = (a * a) % modulo;
                n >>= 1;
            }
            return result;
        }

        private long pow(long a, long n) {
            if (n == 0) return 1;
            if (n % 2 == 0) {
                long ans = pow(a, n / 2);
                return ans * ans;
            } else {
                return a * pow(a, n - 1);
            }
        }

        private void closeStreams() {
            in.close();
            out.close();
        }

        @Override
        public void run() {
            solve();
            closeStreams();
        }

        private final FastScanner in = new FastScanner();
        private final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    }


    public static void main(String[] args) {
        Thread thread = new Thread(null, new Solution(), "solution", 1 << 27);
        thread.setPriority(Thread.MAX_PRIORITY);
        thread.start();
    }


    public static class FastScanner {

        private BufferedReader br;
        private StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }
}