#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define qwq 200007
#define inf 20051113
int n;
struct p{
	int val,num;
	int ans;
}a[qwq];
bool cmp1(p x,p y){
	if(x.val!=y.val)return x.val<y.val;
	return x.num<y.num;
}
bool cmp2(p x,p y){
	return x.num<y.num;
}
struct tree{
	int l,r;
	ll sum,maxn,minn;
	ll tag;
}tr[qwq<<2];
ll sum[qwq];
void pushup(int cnt){
	tr[cnt].sum=tr[cnt<<1].sum+tr[cnt<<1|1].sum;
	tr[cnt].maxn=std::max(tr[cnt<<1].maxn,tr[cnt<<1|1].maxn);
	tr[cnt].minn=std::min(tr[cnt<<1].minn,tr[cnt<<1|1].minn);
	return ;
}
void pushdown(int cnt){
	tr[cnt<<1].sum+=tr[cnt].tag*(tr[cnt<<1].r-tr[cnt<<1].l+1);
	tr[cnt<<1|1].sum+=tr[cnt].tag*(tr[cnt<<1|1].r-tr[cnt<<1|1].l+1);
	tr[cnt<<1].maxn+=tr[cnt].tag;
	tr[cnt<<1|1].maxn+=tr[cnt].tag;
	tr[cnt<<1].minn+=tr[cnt].tag;
	tr[cnt<<1|1].minn+=tr[cnt].tag;
	tr[cnt<<1].tag+=tr[cnt].tag;
	tr[cnt<<1|1].tag+=tr[cnt].tag;
	tr[cnt].tag=0;
}
void build(int l,int r,int cnt){
	tr[cnt].l=l;tr[cnt].r=r;
	tr[cnt].minn=inf;
	tr[cnt].maxn=-inf;
	tr[cnt].tag=0;
	if(l==r){
		tr[cnt].sum=sum[l];
		tr[cnt].maxn=sum[l];
		tr[cnt].minn=sum[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,cnt<<1);
	build(mid+1,r,cnt<<1|1);
	pushup(cnt);
	return ;
}
void add(int l1,int r1,int cnt,int v){
	int l=tr[cnt].l,r=tr[cnt].r;
	if(l1<=l&&r<=r1){
		tr[cnt].sum+=(r-l+1)*v;
		tr[cnt].maxn+=v;
		tr[cnt].minn+=v;
		tr[cnt].tag+=v;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(cnt);
	if(l1<=mid)add(l1,r1,cnt<<1,v);
	if(mid+1<=r1)add(l1,r1,cnt<<1|1,v);
	pushup(cnt);
	return ;
}
int get_maxn(int l1,int r1,int cnt){
	int l=tr[cnt].l,r=tr[cnt].r;
	if(l1<=l&&r<=r1){
		return tr[cnt].maxn;
	}
	pushdown(cnt);
	int mid=(l+r)>>1;
	int ans=-inf;
	if(l1<=mid)ans=std::max(ans,get_maxn(l1,r1,cnt<<1));
	if(mid+1<=r1)ans=std::max(ans,get_maxn(l1,r1,cnt<<1|1));
	return ans;
}
int get_minn(int l1,int r1,int cnt){
	int l=tr[cnt].l,r=tr[cnt].r;
	if(l1<=l&&r<=r1){
		return tr[cnt].minn;
	}
	pushdown(cnt);
	int mid=(l+r)>>1;
	int ans=inf;
	if(l1<=mid)ans=std::min(ans,get_minn(l1,r1,cnt<<1));
	if(mid+1<=r1)ans=std::min(ans,get_minn(l1,r1,cnt<<1|1));
	return ans;
}
int main(){
	scanf("%d",&n);
	int minn=1;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].val);
		a[i].num=i;
		if(a[i].val<a[minn].val){
			minn=i;
		}
	}
	for(int i=1;i<=n;++i){
		sum[i+1]=sum[i];
		if(i!=minn)++sum[i+1];
	}
	build(1,n+1,1);
	std::sort(a+1,a+n+1,cmp1);
	int last=1;
	for(int i=1;i<=n;++i){
		a[i].ans=std::max(a[i].ans,(get_maxn(a[i].num+1,n+1,1)-get_minn(1,a[i].num+1,1)+1+1+1)/2-1);
	//	printf("%d %d %d\n",a[i].val,get_maxn(a[i].num+1,n+1,1),get_minn(1,a[i].num+1,1));
		if(i==n)break;
		add(a[i+1].num+1,n+1,1,-1);
		if(a[i+1].val==a[i].val){
			add(a[i].num+1,n+1,1,1);
		}
		else {
			for(int j=last;j<=i-1;++j)add(a[j].num+1,n+1,1,-2);
			add(a[i].num+1,n+1,1,-1);
			last=i+1;
		}
	}
	std::sort(a+1,a+n+1,cmp2);
//	for(int i=1;i<=n;++i){
//		printf("%d ",a[i].ans);
//	}
//	putchar('\n');
	for(int i=1;i<=n;++i){
		sum[i+1]=sum[i];
		if(i!=minn)++sum[i+1];
	}
	build(1,n+1,1);
	std::sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;++i){
		if(a[i].val!=a[i-1].val){
			for(int j=i+1;j<=n;++j){
				if(a[j].val!=a[i].val)break;
				add(a[j].num+1,n+1,1,-2);
			}
		}
		a[i].ans=std::max(a[i].ans,(get_maxn(1,a[i].num+1,1)-get_minn(a[i].num+1,n+1,1))/2);
		
	//	printf("%d %d %d\n",a[i].val,get_maxn(1,a[i].num+1,1),get_minn(a[i].num+1,n+1,1));
		if(i==n)break;
		add(a[i].num+1,n+1,1,-1);
		if(a[i+1].val==a[i].val){
			add(a[i+1].num+1,n+1,1,1);
		}
		else add(a[i+1].num+1,n+1,1,-1);
	}
	std::sort(a+1,a+n+1,cmp2);
	for(int i=1;i<=n;++i){
		printf("%d ",a[i].ans);
	}
	putchar('\n');
	return 0;
}