← 返回题目列表

Codeforces · 547/B

B. 迈克和脚

中文机器翻译题面 查看原题

迈克是“What-The-Fatherland”国家的总统。除了迈克之外,这个国家还有 n 只熊。他们全部站成一排,从左到右编号为 1 到 n。第 i 只熊正好有 ai 英尺高。

一组熊是该行的非空连续段。一个群体的大小是该群体中熊的数量。一个群体的力量是该群体中熊的最小高度。

Mike 很想知道对于每个 x,使得 1 ≤ x ≤ n 的所有大小为 x 的组中的最大强度。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 2 × 105),即熊的数量。

第二行包含 n 个以空格分隔的整数,a1, a2, ..., an (1 ≤ ai ≤ 109),熊的高度。

输出

在一行中打印 n 个整数。对于从 1 到 n 的每个 x,打印大小为 x 的所有组中的最大强度。

示例

输入 #1

10
1 2 3 4 5 4 3 2 1 6

输出 #1

6 4 4 3 3 2 2 1 1 1