Codeforces Round #305 (Div. 1) problem: (B) Mike and Feet

#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct node{
    int a,l,r;
};
node arr[200005];

bool compare (node x, node y){
    return x.a > y.a;
}

int n;
stack<int> s;

int main(){
    scanf("%d",&n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i].a);

    //left
    for (int i = 0; i < n; ++i)
    {
        if(s.empty())
            s.push(i);
        else{
            int top = s.top();
            if(arr[top].a <= arr[i].a)
                s.push(i);
            else{
                while(arr[top].a > arr[i].a){
                    arr[top].r = i;
                    s.pop();
                    if(s.empty())
                        break;
                    top  = s.top();
                }
                s.push(i);
            }
        }
    }
    while(!s.empty()){
        int top = s.top();
        arr[top].r = n;
        s.pop();
    }

    //left
    for (int i = n-1; i >=0 ; --i)
    {
        if(s.empty())
            s.push(i);
        else{
            int top = s.top();
            if(arr[top].a <= arr[i].a)
                s.push(i);
            else{
                while(arr[top].a > arr[i].a){
                    arr[top].l = i;
                    s.pop();
                    if(s.empty())
                        break;
                    top  = s.top();
                }
                s.push(i);
            }
        }
    }
    while(!s.empty()){
        int top = s.top();
        arr[top].l = -1;
        s.pop();
    }

    for (int i = 0; i < n; ++i)
    {
        arr[i].r -= (i+1);
        arr[i].l = i - arr[i].l - 1;
    }

    //find ans
    sort(arr, arr+n, compare);
    int now = 0;
    for (int x = 1; x <= n; ++x)
    {
        while(arr[now].l + arr[now].r + 1 < x){
            now++;
        }  
        printf("%d ", arr[now].a);
    }
    printf("\n");

}