迈克是“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