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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Stack;
import java.util.Vector;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author dauom
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    BMikeAndFeet solver = new BMikeAndFeet();
    solver.solve(1, in, out);
    out.close();
  }

  static final class BMikeAndFeet {
    public final void solve(int testNumber, InputReader in, PrintWriter out) {
      int n = in.nextInt();
      int[] a = in.nextIntArray(n);

      Stack<Integer> stk = new Stack<>();
      int[] prv = new int[n];
      for (int i = 0; i < n; i++) {
        while (!stk.isEmpty() && a[stk.peek()] >= a[i]) {
          stk.pop();
        }
        if (stk.isEmpty()) {
          prv[i] = -1;
        } else {
          prv[i] = stk.peek();
        }
        stk.push(i);
      }
      stk.clear();

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

        int size = nxt - prv[i] - 1;
        s[i] = new int[] {-a[i], -size};
      }

      Arrays.sort(s, Comparators.pairIntArr);
      int[] ans = new int[n];
      int lastSize = 0;
      for (int[] p : s) {
        int v = -p[0];
        int size = -p[1];
        if (size > lastSize) {
          for (int k = lastSize + 1; k <= size; k++) {
            ans[k - 1] = v;
          }
          lastSize = size;
        }
      }

      out.println(StringUtils.join(ans));
    }
  }

  static final class Comparators {
    public static final Comparator<int[]> pairIntArr =
        (x, y) -> x[0] == y[0] ? compare(x[1], y[1]) : compare(x[0], y[0]);

    private static final int compare(final int x, final int y) {
      return x < y ? -1 : (x == y ? 0 : 1);
    }
  }

  static class StringUtils {
    private StringUtils() {
      throw new RuntimeException("DON'T");
    }

    public static final String joinRange(String delimiter, int from, int to, int[] a) {
      if (from > to) {
        return "";
      }
      StringBuilder sb = new StringBuilder();
      sb.append(a[from]);
      for (int i = from + 1; i <= to; i++) {
        sb.append(delimiter).append(a[i]);
      }
      return sb.toString();
    }

    public static final String join(int... a) {
      return joinRange(" ", 0, a.length - 1, a);
    }
  }

  static final class InputReader {
    private final InputStream stream;
    private final byte[] buf = new byte[1 << 18];
    private int curChar;
    private int numChars;

    public InputReader() {
      this.stream = System.in;
    }

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

    private int read() {
      if (this.numChars == -1) {
        throw new UnknownError();
      } else {
        if (this.curChar >= this.numChars) {
          this.curChar = 0;

          try {
            this.numChars = this.stream.read(this.buf);
          } catch (IOException ex) {
            throw new InputMismatchException();
          }

          if (this.numChars <= 0) {
            return -1;
          }
        }

        return this.buf[this.curChar++];
      }
    }

    public final int nextInt() {
      int c;
      for (c = this.read(); isSpaceChar(c); c = this.read()) {}

      byte sgn = 1;
      if (c == 45) { // 45 == '-'
        sgn = -1;
        c = this.read();
      }

      int res = 0;

      while (c >= 48 && c <= 57) { // 48 == '0', 57 == '9'
        res *= 10;
        res += c - 48; // 48 == '0'
        c = this.read();
        if (isSpaceChar(c)) {
          return res * sgn;
        }
      }

      throw new InputMismatchException();
    }

    private static boolean isSpaceChar(final int c) {
      return c == 32 || c == 10 || c == 13 || c == 9
          || c == -1; // 32 == ' ', 10 == '\n', 13 == '\r', 9 == '\t'
    }

    public final int[] nextIntArray(final int n) {
      int[] arr = new int[n];
      for (int i = 0; i < n; i++) {
        arr[i] = nextInt();
      }
      return arr;
    }
  }
}
