Codat

#include <fstream>

using namespace std;
ifstream cin("codat.in");
ofstream cout("codat.out");
#define MAXN 1000000
int v[MAXN],st[MAXN],poz[MAXN];
int raspsp[MAXN];
int raspdp[MAXN];
int main()
{
    int n,i,capat;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>v[i];
    }
    ///stanga
    poz[0]=0;
    capat=0;
    raspsp[0]=-1;
    for(i=1;i<n;i++){
        if(st[capat]>v[i]){
            raspsp[i]=poz[capat];
            st[capat+1]=v[i];
            poz[capat+1]=i;
            capat++;
        }else{
            while(capat>=0 && st[capat]<=v[i]){
                capat--;
            }
            if(capat==-1){
                st[0]=v[i];
                poz[0]=i;
                capat=0;
                raspsp[i]=-1;
            }else{
                raspsp[i]=poz[capat];
                st[capat+1]=v[i];
                poz[capat+1]=i;
                capat++;
            }
        }
    }
    ///dr
    st[0]=v[n-1];
    poz[0]=n-1;
    raspdp[n-1]=-1;
    capat=0;
    for(i=n-2;i>=0;i--){
        if(st[capat]>v[i]){
            raspdp[i]=poz[capat];
            st[capat+1]=v[i];
            poz[capat+1]=i;
            capat++;
        }else{
            while(capat>=0 && st[capat]<=v[i]){
                capat--;
            }
            if(capat==-1){
                st[0]=v[i];
                poz[0]=i;
                capat=0;
                raspdp[i]=-1;
            }else{
                raspdp[i]=poz[capat];
                st[capat+1]=v[i];
                poz[capat+1]=i;
                capat++;
            }
        }
    }
    for(i=0;i<n;i++){
        if(raspdp[i]==-1 && raspsp[i]==-1)
            cout<<"-1 ";
        else if(raspdp[i]==-1){
            cout<<raspsp[i]+1<<" ";
        }else if(raspsp[i]==-1){
            cout<<raspdp[i]+1<<" ";
        }else if(raspdp[i]-i<=i-raspsp[i]){
            cout<<raspdp[i]+1<<" ";
        }else{
            cout<<raspsp[i]+1<<" ";
        }
    }
    return 0;
}