SMMR-Chi-006: Window Sizing Puzzle

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
int ar[N], mx[N];

int main(){

    int n;
    scanf("%d", &n);

    for(int i=1;i<=n;i++)
        scanf("%d", &ar[i]);
    ar[n + 1] = 0;

    stack <int> st;
    for(int i=1;i<=n+1;i++){
        while(!st.empty() and ar[st.top()] > ar[i]){
            int idx = st.top(); st.pop();
            int len = 0;
            if(st.empty()) len = i - 1;
            else len = i - st.top() - 1;
            mx[len] = max(mx[len], ar[idx]);
        }
        st.push(i);
    }

    for(int i=n;i>=1;i--)
        mx[i] = max(mx[i], mx[i + 1]);

    for(int i=1;i<=n;i++)
        printf("%d ", mx[i]);

    return 0;
}