Mike and Feet

题面翻译

题目描述

给定一个大小为 $n$ 的数列 $a$。

本题中，我们定义数列 $a$ 的一个连续子序列的区间强度为该子序列中所有元素的最小值。

比如，对于一个大小为 $5$ 的数列 $1,2,3,4,5$ 来说，其连续子序列 $1,2,3$ 对应的区间强度为 $1$；其连续子序列 $3,4,5$ 对应的区间强度为 $3$。

现在你需要求出对于任意一个 $k(1 \le k \le n)$，所有长度为 $k$ 的连续子序列对应的区间强度的最大值。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \times 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$，两两之间以一个空格分隔。

输出格式

输出共一行，包含 $n$ 个整数，两两之间以一个空格分隔。

其中第 $k$ 个整数表示数列 $a$ 的所有长度为 $k$ 的连续子序列对应的区间长度的最大值。

题目描述

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 $a_{i}$ 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$ .

输入格式

The first line of input contains integer $n$ ( $1<=n<=2×10^{5}$ ), the number of bears.

The second line contains $n$ integers separated by space, $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{9}$ ), heights of bears.

输出格式

Print $n$ integers in one line. For each $x$ from $1$ to $n$ , print the maximum strength among all groups of size $x$ .

样例 #1

样例输入 #1

10
1 2 3 4 5 4 3 2 1 6

样例输出 #1

6 4 4 3 3 2 2 1 1 1