#include<bits/stdc++.h>
#define val first
#define id second
using namespace std;
const int N=1e6+10;
int a[N],n,ans[N],r;
pair<int,int> x[N];

struct SegTree{
	int mx[N],mn[N],tag[N];
	#define ls (rt<<1)
	#define rs ((rt<<1)|1)
	#define middef int mid=(l+r)>>1
	void _add(int rt,int v){tag[rt]+=v,mx[rt]+=v,mn[rt]+=v;}
	void push_down(int rt){if(tag[rt])_add(ls,tag[rt]),_add(rs,tag[rt]),tag[rt]=0;}
	void push_up(int rt){
		mx[rt]=max(mx[ls],mx[rs]);
		mn[rt]=min(mn[ls],mn[rs]);
	}
	void add(int L,int R,int v,int l=0,int r=n,int rt=1){
		if(r<L||R<l)return;
		if(L<=l&&r<=R)return _add(rt,v);
		middef;push_down(rt);
		add(L,R,v,l,mid,ls);
		add(L,R,v,mid+1,r,rs);
		push_up(rt);
	}
	void build(int l=0,int r=n,int rt=1){
		if(l==r)return _add(rt,a[l]);
		middef;
		build(l,mid,ls),build(mid+1,r,rs);
		push_up(rt);
	}
	int get_max(int L,int R,int l=0,int r=n,int rt=1){
		if(r<L||R<l)return -1e9;
		if(L<=l&&r<=R)return mx[rt];
		middef;push_down(rt);
		return max(get_max(L,R,l,mid,ls),get_max(L,R,mid+1,r,rs));
	}
	int get_min(int L,int R,int l=0,int r=n,int rt=1){
		if(r<L||R<l)return 1e9;
		if(L<=l&&r<=R)return mn[rt];
		middef;push_down(rt);
		return min(get_min(L,R,l,mid,ls),get_min(L,R,mid+1,r,rs));
	}
}s,t;

int main(){
	cin>>n;
	for(int i=1;i<=n;++i)cin>>x[i].val,x[i].id=i,a[i]=a[i-1]+1;
	s.build();
	for(int i=1;i<=n;++i)a[i]=a[i-1]-1;
	t.build();
	sort(x+1,x+n+1);
	for(int i=1;i<=n;i=r+1){
		r=i;
		while(r<=n&&x[r].val==x[i].val)r++;
		r--;
		for(int j=i;j<=r;++j)
			t.add(x[j].id,n,2);
		for(int j=i;j<=r;++j){
			int res=t.get_max(x[j].id,n)-t.get_min(0,x[j].id-1)-1;
			res/=2;
			ans[x[j].id]=max(ans[x[j].id],res);
			res=s.get_max(x[j].id,n)-s.get_min(0,x[j].id-1);
			res/=2;
			ans[x[j].id]=max(ans[x[j].id],res);			
		}
		for(int j=i;j<=r;++j)
			s.add(x[j].id,n,-2);
	}
	for(int i=1;i<=n;++i)cout<<ans[i]<<" ";
}
