Mike是What-The-Fatherland国家的总统。除了Mike,这个国家还有n只熊。他们都站成一排,从左到右从1到n编号。这只熊正好有ai英尺高。
一组熊是一行的非空连续段。一个群体的规模就是这个群体中熊的数量。一个群体的力量是该群体中熊的最低高度。
Mike很好奇,对于每一个x,使1≤x≤n在所有大小x的组中最大强度。
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.
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.
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
Output
6 4 4 3 3 2 2 1 1 1