解题思路

给定一行共 n 人，每人有能力值 a[i]。对所有连续长度为 x 的小组，该组能力值定义为组内最小值；题目要求对所有 1≤x≤n，输出“长度为 x 的所有小组能力值中的最大值”。

核心做法是用 单调栈 预处理每个元素作为“组内最小值”时所能覆盖的最大窗口长度：

1. 对每个位置 i，找到

   • pre[i]：i 左侧 第一个严格更小 的位置（值 < a[i]），不存在记为 -1；

题目内容

我们可能听过“短板效应”这一说法:一只水桶能盛多少水，并不取决于最长的那块木板，而是取决于最短的那块木板。

小明在完成某个小组任务时，也出现了类似的情况。小明的班级有 $n$ 个人排成一行，每个人有一个能力值 $a_i$ 每连续 $i$ 个人都在一个大小为 $i$ 的组里，一个人会在很多个组。例如 $1,2,3,4,5$，五个人依次排成一行，有$1,2,3;2,3,4;3,4,5$ 这三个大小为 $3$ 的组，有 $1,2,3,4;2,3,4,5$ 这两个大小为 $4$ 的组。一个组的能力值为组里所有人能力值的最小值，小明作为班长想对于所有 $1≤x≤n$ 求出所有大小为 $x$ 的组的能力值的最大值为多少。

输入描述

第一行一个正整数 $n$ ，表示班级中的人数。

$(1≤n≤100000)$

接下来一行 $n$ 个整数，表示 $a_1,a_2,…,a_n$ ，依次表示每个人的能力值。$(1≤a_i≤10^9)$

输出描述

输出一行 $n$ 个整数，分别表示大小为 $1,2,...,n$ 的所有组能力值最大值为多少。

样例1

输入

6
4 5 3 1 3 4

输出

5 4 3 1 1 1

说明

大小为 $1$ 的分组就是每个人自己，每个组最大值就是)。

大小为 $2$ 的分组的能力值分别是 $4,5;5,3;3,1;1,3;3,4$,其中 $4,5$ 这组能力为 $4$ ，最大。

大小为 $3$ 的分组的能力值分别是 $4,5,3;5,3,1;3,1,3;1,3,4$，其中 $4,5,3$ 这组能力值为 $3$ ，最大。

大小为 $4,5,6$ 的分组同理。