时间限制：1000ms　内存限制：512MB

题目描述

会展中心有一条长长的展廊，靠墙一字排开 $n$ 个展柜，编号 $1$ 到 $n$，第 $i$ 个展柜高 $h_i$ 厘米。展廊上方要加装一批遮光帘，用来保护怕光的展品。遮光帘按长度定制，一条长度为 $len$ 的帘子恰好能连续遮住 $len$ 个展柜，从左到右一格不多一格不少，挂在哪个位置由馆方选择。

定制部给的报价规则很特别：帘子的价格不取决于帘子本身，而取决于被遮住的那一段展柜——一条帘子挂定之后，被遮住的 $len$ 个展柜里最高的那个有多高，这条帘子的"基准高度"就是多少。报价单上基准高度一档一个价，基准高度越低，价格越便宜。馆方采购时自然关心一个问题：长度定为 $len$ 的帘子，挂在什么位置基准高度最低？也就是在所有连续 $len$ 个展柜的组合里，找"最高展柜高度"最小的那一处，把这个最小值报给定制部。

挂帘的几条规矩再交代一遍。第一，帘子必须连续遮满 $len$ 个展柜，不许隔空、不许错位，两端恰好对齐展柜边缘。第二，挂的位置不限，贴着展廊哪一头都行，也可以居中，一种长度还可以今天挂这、明天挂那，报价只看能不能挂出那个最低基准高度。第三，被遮的展柜里最高的那个怎么算，只认展柜本身的高度，柜子里的展品高低不问。第四，一种长度只报一个数——所有挂法里最小的那个基准高度，位置不用上报。

展廊的展柜高度参差不齐，有的地段普遍矮，有的地段杵着一两个高柜。长度不同的帘子，最低基准高度往往出现在完全不同的位置：短帘子也许能卡进矮柜扎堆的空当，长帘子避不开某些高柜，报价值随长度一路上去。每个长度的确切数值，得一格一格量过才知道。

这项工作以前是库管员拿卷尺量的。每换一种帘长，他就把展廊从头到尾走一遍，每走一格抬头看一眼，记下这一段里最高的柜子，走完一圈挑出最小的数。帘长从 $1$ 到 $n$ 有 $n$ 种，他就要走 $n$ 圈，展柜多的时候一天量不完，还常常记串行。上一回报价单就出了错：有一种帘长的基准高度抄串了一行，定制部按错误的档位报价，馆方多付了一笔，对账对了一个星期才扯清楚。打那以后，馆长立了规矩，报价数字必须能复核、能倒查。这次听说程老师有办法，干脆把量活的差事整个转了过来。

程老师拿到的是展柜清单：$n$ 个展柜各自的高度。请替定制部算出全部 $n$ 种帘长的答案——对每个 $len = 1, 2, \ldots, n$，给出长度为 $len$ 的帘子能拿到的最低基准高度。这份清单会附在采购合同的附件里，馆方、定制部各执一份，数字对不上时要拿它复核。

输入格式

第一行一个整数 $n$，表示展柜数量。

第二行 $n$ 个整数 $h_1, h_2, \ldots, h_n$，表示各展柜的高度（厘米）。

输出格式

输出 $n$ 行，第 $len$ 行一个整数，表示长度为 $len$ 的遮光帘的最低基准高度。

数据范围

• 特殊性质 A：所有展柜的高度互不相同。
• 对于全部数据，$1 \le n \le 2 \times 10^5$，$1 \le h_i \le 10^9$。

样例

样例 1

输入：

5
1 3 2 5 4

输出：

1
3
3
5
5

解释：$len = 1$ 时遮单个展柜，最矮的是 $1$。$len = 2$ 时，遮住 $1, 3$ 最高是 $3$，遮住 $3, 2$ 最高是 $3$，再往后最高都是 $5$，最低基准高度是 $3$。$len = 3$ 时，遮住 $1, 3, 2$ 最高仍是 $3$。$len \ge 4$ 时，无论怎么挂都躲不开那个高 $5$ 的展柜，答案就是 $5$。

样例 2

输入：

4
2 2 2 2

输出：

2
2
2
2

解释：四个展柜一样高，帘子无论多长、挂在哪里，遮住的最高展柜都是 $2$，四种长度的答案清一色是 $2$。

样例 3

输入：

6
5 1 4 2 3 6

输出：

1
3
4
4
5
6

解释：$len = 1$ 最矮是 $1$。$len = 2$ 时各组合的最高值依次是 $5, 4, 4, 3, 6$，最低 $3$。$len = 3$ 时依次是 $5, 4, 4, 6$，最低 $4$。$len = 4$ 时依次是 $5, 4, 6$，最低 $4$。$len = 5$ 时依次是 $5, 6$，最低 $5$。$len = 6$ 只有整廊一种挂法，最高是 $6$。