#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;//注意修改大小
long long read(){long long x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
ll qpow(ll x,ll q,ll Mod){ll ans=1;while(q){if(q&1)ans=ans*x%Mod;q>>=1;x=(x*x)%Mod;}return ans%Mod;}
int n;
struct Seg_Tree{
	struct Tree{
		int l,r,w,lazy,lmax,rmax;
	}tree[maxn*4];
	void pushup(int id){
		tree[id].w=tree[id*2].w+tree[id*2+1].w;
        tree[id].lmax=max(tree[id*2].lmax,tree[id*2].w+tree[id*2+1].lmax);
        tree[id].rmax=max(tree[id*2+1].rmax,tree[id*2+1].w+tree[id*2].rmax);
	}
	// void pushdown(int id){
	// 	tree[id*2].w=tree[id*2].w+(tree[id*2].r-tree[id*2].l+1)*tree[id].lazy;
	// 	tree[id*2+1].w=tree[id*2+1].w+(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].lazy;
	// 	tree[id*2].lazy=tree[id*2].lazy+tree[id].lazy;tree[id*2+1].lazy=tree[id*2+1].lazy+tree[id].lazy;
	// 	tree[id].lazy=0;
	// }
	void build(int id,int l,int r){
		tree[id].l=l;tree[id].r=r;
		if(l==r){
			tree[id].lazy=0;tree[id].w=tree[id].lmax=tree[id].rmax=-1;
			return;
		}
		int mid=(l+r)/2;
		build(id*2,l,mid);build(id*2+1,mid+1,r);
		pushup(id);
	}
	void update(int id,int l,int r,int w){//更新[l,r]每个点+w 
		if(tree[id].l>=l&&tree[id].r<=r){
			tree[id].w=tree[id].lmax=tree[id].rmax=w;
			// tree[id].lazy+=w;
			return;
		}
		// if(tree[id].lazy)pushdown(id);
		int mid=(tree[id].l+tree[id].r)/2;
		if(l<=mid)update(id*2,l,r,w);
		if(r>mid)update(id*2+1,l,r,w);
		pushup(id);
	}
	Tree query(int id,int l,int r){//查询[l,r]区间和 
		if(tree[id].l==l&&tree[id].r==r)return tree[id];
		// if(tree[id].lazy)pushdown(id);
		int mid=(tree[id].l+tree[id].r)/2;
		if(r<=mid)return query(id*2,l,r);
		else if(l>mid)return query(id*2+1,l,r);
        else{
            Tree node,lson,rson;
            lson=query(id*2,l,mid);rson=query(id*2+1,mid+1,r);
            node.w=lson.w+rson.w;
            node.lmax=max(lson.w+rson.lmax,lson.lmax);
            node.rmax=max(rson.w+lson.rmax,rson.rmax);
            return node;
        }
	}
}t;
struct Node{
    int w,id;
    bool operator < (Node x)const{
        if(x.w==w)return id<x.id;
        return w<x.w;
    }
}a[maxn];
int ans[maxn];
int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].w,a[i].id=i;
    sort(a+1,a+1+n);
    for(int opt=0;opt<=1;opt++){
        t.build(1,1,n);
        int opt1=1,opt2=1;
        for(int i=1;i<=n;i++){
            while(opt1<=n&&a[opt1].w==i){
                t.update(1,a[opt1].id,a[opt1].id,1);
                opt1++;
            }
            while(opt2<=n&&a[opt2].w==i){
                Seg_Tree::Tree l=t.query(1,1,a[opt2].id);
                Seg_Tree::Tree r=t.query(1,a[opt2].id,n);
                ans[a[opt2].id]=max(ans[a[opt2].id],l.rmax+r.lmax-2+(opt==1));
                opt2++;
            }
        }
        for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);
        for(int i=1;i<=n;i++)a[i].w=n-a[i].w+1;
    }
    for(int i=1;i<=n;i++)cout<<ans[i]/2<<' ';cout<<endl;
    return 0;
}