#include <bits/stdc++.h>

using namespace std;
int n,sol[200005];
int mic[1000005][3],mare[1000005][3],valmic[1000005],valmare[1000005];
struct date
{
    int poz,val;
} v[200005];
bool comp(date a, date b)
{
    return a.val<b.val;
}
void prop(int arb[1000005][3], int nod)
{
    int x=arb[nod][2];
    for(auto i:{0,1,2})
    {
        arb[nod*2][i]+=x;
        arb[nod*2+1][i]+=x;
    }
}
void update(int arb[1000005][3],int nod,int st,int dr,int a, int b,int val)
{
    if(arb[nod][2]!=0)
    {
        if(st!=dr)
            prop(arb,nod);
        arb[nod][2]=0;
    }
    if(st>=a&&dr<=b)
    {
        arb[nod][0]+=val;
        arb[nod][1]+=val;
        arb[nod][2]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(arb,nod*2,st,mij,a,b,val);
    if(b>mij)
        update(arb,nod*2+1,mij+1,dr,a,b,val);
    arb[nod][0]=min(arb[nod*2][0],arb[nod*2+1][0]);
    arb[nod][1]=max(arb[nod*2][1],arb[nod*2+1][1]);
}
int minim(int arb[1000005][3],int nod,int st,int dr,int a, int b)
{
    if(arb[nod][2]!=0)
    {
        if(st!=dr)
            prop(arb,nod);
        arb[nod][2]=0;
    }
    if(st>=a&&dr<=b)
        return arb[nod][0];
    int mij=(st+dr)/2;
    int ans=1e18;
    if(a<=mij)
        ans=min(ans,minim(arb,nod*2,st,mij,a,b));
    if(b>mij)
        ans=min(ans,minim(arb,nod*2+1,mij+1,dr,a,b));
    return ans;
}
int maxim(int arb[1000005][3],int nod,int st,int dr,int a, int b)
{
    if(arb[nod][2]!=0)
    {
        if(st!=dr)
            prop(arb,nod);
        arb[nod][2]=0;
    }
    if(st>=a&&dr<=b)
        return arb[nod][1];
    int mij=(st+dr)/2;
    int ans=-1e18;
    if(a<=mij)
        ans=max(ans,maxim(arb,nod*2,st,mij,a,b));
    if(b>mij)
        ans=max(ans,maxim(arb,nod*2+1,mij+1,dr,a,b));
    return ans;
}
void make(int poz,int vmic,int vmare)
{
    update(mic,1,0,n,poz,n,-valmic[poz]);
    update(mare,1,0,n,poz,n,-valmare[poz]);
    valmic[poz]=vmic;
    valmare[poz]=vmare;
    update(mic,1,0,n,poz,n,valmic[poz]);
    update(mare,1,0,n,poz,n,valmare[poz]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].val;
        v[i].poz=i;
    }
    sort(v+1,v+n+1,comp);
    for(int i=1;i<=n;i++)
    {
        valmic[i]=-1,valmare[i]=1;
        update(mic,1,0,n,i,n,-1);
        update(mare,1,0,n,i,n,1);
    }
    for(int p=1;p<=n;p++)
    {
        int nr=v[p].val,poz=v[p].poz;
        if(nr!=v[p-1].val)
        {
            for(int j=p;j<=n&&v[j].val==nr;j++)
                make(v[j].poz,1,1);
            for(int j=p-1;j>=1&&v[j].val==v[p-1].val;j--)
                make(v[j].poz,1,-1);
        }
        make(poz,0,0);
        int dif1=maxim(mare,1,0,n,poz,n)-minim(mare,1,0,n,0,poz-1);
        int dif2=maxim(mic,1,0,n,poz,n)-minim(mic,1,0,n,0,poz-1);
        int dif=max(dif1,dif2);
        // insert formula
        sol[poz]=max(dif1/2+dif1%2,dif2/2);
        make(poz,1,1);
    }
    for(int i=1;i<=n;i++)
        cout<<sol[i]<<" ";
    return 0;
}
