CF547B.Mike and Feet

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 a__i feet high.

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.

Mike 是“什么老爸国”（What-The-Fatherland）的总统。除了 Mike 之外，该国还有 $n$ 只熊。它们全部站成一排，从左到右依次编号为 $1$ 到 $n$。第 $i$ 只熊的身高恰好为 $a_i$ 英尺。

一组熊是指该行中一个非空且连续的子段。该组的大小即为其中熊的数量；该组的强度定义为该组中熊的最小身高。

Mike 好奇地想知道：对每个满足 $1 \le x \le n$ 的 $x$，所有大小为 $x$ 的组中所能达到的最大强度是多少。

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, _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109), heights of bears.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示熊的数量。

第二行包含 $n$ 个由空格分隔的整数 $a_1,\ a_2,\ \dots,\ a_n$（$1 \leq a_i \leq 10^9$），表示每只熊的高度。

Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.

在一行中输出 n 个整数。对于每个从 1 到 n 的 x，输出所有大小为 x 的组中的最大强度值。