Given an array of n positive integers, for each window size k from 1 to n do the following: look at every contiguous window of exactly k elements, take the minimum of each window, and record the largest of those minimums. Output these n values, one for each k in order.
An efficient solution uses a monotonic stack to find, for each element, the longest window in which it is the minimum, then propagates results from larger window sizes down to smaller ones.
Input format
Line 1: an integer n.
Line 2: n space-separated positive integers.
Output format
n space-separated integers on one line: for each window size k = 1, 2, ..., n, the maximum window-minimum.
Constraints
- 1 <= n <= 100000
- 1 <= value <= 1000000000