文件名

输入文件："Interval minimum value.in"

输出文件："Interval minimum value.out"

题目描述

给定一个长度为 $n$ 的正整数数组 $a_1,a_2,...,a_n$

定义 $f(l,r)$ 表示 $min(a_l,a_{l+1},...,a_r)$

定义 $g(x)$ 表示 $max(f(1,x),f(2,x+1),...,f(n-x+1,n))$

你需要输出 $g(1),g(2),...,g(n)$ 的值

输入格式

第一行输入一个正整数 $n$ ，表示数组的长度

第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n$

输出格式

一行输出 $n$ 个数 $g(1),g(2),...,g(n)$ ，用空格分隔

样例

10
1 2 3 4 5 4 3 2 1 6

6 4 4 3 3 2 2 1 1 1

20
6 20 1 14 17 15 11 18 17 5 13 7 6 9 3 13 19 20 3 3

20 19 14 11 11 11 5 5 5 5 5 3 3 3 3 3 3 1 1 1

附件：点击下载

数据范围

对于30%的数据，$1<=n<=1000$

对于全部的数据，$1<=n<=10^6,1<=a_i<=10^9$