TAChi-T006: Window Sizing Puzzle

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int arr[N], ans[N];

int main(){

    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
        ans[i] = -1;
    }
    arr[n + 1] = 0;
    stack<int> stk;
    for(int i = 1; i <= n + 1; ++i){
        while(!stk.empty() && arr[stk.top()] > arr[i]){
            int cur = stk.top();
            stk.pop();
            int prv = stk.empty() ? 0 : stk.top();
            int idx = i - prv - 1;
            ans[idx] = max(ans[idx], arr[cur]);
        }
        stk.push(i);
    }
    for(int i = n; i >= 1; --i){
        ans[i] = max(ans[i], ans[i + 1]);
    }
    for(int i = 1; i <= n; ++i){
        cout << ans[i] << ' ';
    }

    return 0;
}