A9933 | 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$ .

The first line of input contains integer $n$ ( $1<=n<=2×10^{5}$ ), the number of bears.

The second line contains $n$ integers separated by space, $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{9}$ ), heights of bears.

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