#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef double db;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define low(x) ((x)&-(x))
#define all(x) x.begin(),x.end()
#define mp make_pair
#define X first
#define Y second
#ifdef _DEBUG
	const int N=1e3+10;
#else
	const int N=1e6+10;
#endif
const ll mod=1e9+7;
//const ll mod=998244353;
inline ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
inline ll q_pow(ll a,ll x){ll ans=1,tmp=a;while(x){if(x&1)(ans*=tmp)%=mod;(tmp*=tmp)%=mod;x>>=1;}return ans;}
template<typename T> inline void re(T &N){int f=1;char c;while((c=getchar())< '0'||c> '9')if(c=='-')f=-1;N=c-'0';while((c=getchar())>='0'&&c<='9')N=N*10+c-'0';N*=f;}
int m,n,t=1,st,en;
int a[N],ans[N];
vector<int>v[N];
pi init[N];
struct SegT{
	pi e[N<<2];
	int tag[N<<2];
	
	inline void push_up(int p)
	{
		e[p].X=max(e[ls(p)].X,e[rs(p)].X);
		e[p].Y=min(e[ls(p)].Y,e[rs(p)].Y);
	}
	void build(int p,int l,int r)
	{
		if(l==r)return e[p]={init[l].X,init[l].X},void();
		int mid=(l+r)>>1;
		build(ls(p),l,mid);
		build(rs(p),mid+1,r);
		push_up(p);
	}
	inline void push_down(int p)
	{
		if(tag[p])
		{
			e[ls(p)].X+=tag[p];e[ls(p)].Y+=tag[p];
			e[rs(p)].X+=tag[p];e[rs(p)].Y+=tag[p];
			tag[ls(p)]+=tag[p];tag[rs(p)]+=tag[p];
			tag[p]=0;
		}
	}
	void update(int p,int l,int r,int L,int R,int k)
	{
		if(L<=l&&r<=R)
		{
			e[p].X+=k;e[p].Y+=k;
			tag[p]+=k;return;
		}
		push_down(p);
		int mid=(l+r)>>1;
		if(L<=mid)update(ls(p),l,mid,L,R,k);
		if(mid< R)update(rs(p),mid+1,r,L,R,k);
		push_up(p);
	}
	pi query(int p,int l,int r,int L,int R)
	{
		pi ans={-1e9,1e9};
		if(L<=l&&r<=R)return e[p];
		push_down(p);
		int mid=(l+r)>>1;
		if(L<=mid)
		{
			pi tmp=query(ls(p),l,mid,L,R);
			ans.X=max(ans.X,tmp.X);
			ans.Y=min(ans.Y,tmp.Y);
		}
		if(mid< R)
		{
			pi tmp=query(rs(p),mid+1,r,L,R);
			ans.X=max(ans.X,tmp.X);
			ans.Y=min(ans.Y,tmp.Y);
		}
		return ans;
	}
}tr1,tr2;

int main()
{
	#ifdef _DEBUG
		freopen("data.txt","r",stdin);
	#endif
	re(n);
	for(int i=1;i<=n;i++)re(a[i]),v[a[i]].push_back(i);
	for(int i=1;i<=n+1;i++)init[i].X=init[i-1].X+1;
	for(int i=n;i>=0;i--)init[i].Y=init[i+1].Y+1;
	tr1.build(1,0,n+1);
	for(int i=0;i<=n+1;i++)swap(init[i].X,init[i].Y);
	tr2.build(1,0,n+1);
	for(int i=1;i<=n;i++)
	{
		for(int j:v[i])
		{
			int ans1=(tr1.query(1,0,n+1,j,j).X-tr1.query(1,0,n+1,0,j-1).X)+(tr2.query(1,0,n+1,j,j).X-tr2.query(1,0,n+1,j+1,n+1).X)-2;
			int ans2=(tr1.query(1,0,n+1,j,j).X-tr1.query(1,0,n+1,0,j-1).Y)+(tr2.query(1,0,n+1,j,j).X-tr2.query(1,0,n+1,j+1,n+1).Y)-2;
			if(ans1&1)ans1=abs((ans1+1)/2);else ans1=abs(ans1/2);
			if(ans2&1)ans2=abs((ans2+1)/2);else ans2=abs(ans2/2);
			ans[j]=max({ans[j],ans1,ans2});
			//clog<<i<<' '<<tr1.query(1,0,n+1,j,j).X<<' '<<tr1.query(1,0,n+1,0,j-1).X<<' '<<tr2.query(1,0,n+1,j,j).X<<' '<<tr2.query(1,0,n+1,j+1,n+1).X<<'\n';
		}
		for(int j:v[i])
		{
			tr1.update(1,0,n+1,j,n+1,-2);
			tr2.update(1,0,n+1,0,j,-2);
		}
		for(int j:v[i])
		{
			int ans1=(tr1.query(1,0,n+1,j,j).X-tr1.query(1,0,n+1,0,j-1).X)+(tr2.query(1,0,n+1,j,j).X-tr2.query(1,0,n+1,j+1,n+1).X)+2;
			int ans2=(tr1.query(1,0,n+1,j,j).X-tr1.query(1,0,n+1,0,j-1).Y)+(tr2.query(1,0,n+1,j,j).X-tr2.query(1,0,n+1,j+1,n+1).Y)+2;
			if(ans1&1)ans1=abs((ans1+1)/2);else ans1=abs(ans1/2);
			if(ans2&1)ans2=abs((ans2+1)/2);else ans2=abs(ans2/2);
			ans[j]=max({ans[j],ans1,ans2});
		}
	}
	for(int i=1;i<=n;i++)printf("%d ",ans[i]);puts("");
}
