#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define lll __int128
#define tp top()
#define fr front()
#define vi vector<int>
#define sz size()
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define mem(a,  b) memset(a,  (b),  sizeof(a))
#define clr(a) memset(a,  0,  sizeof(a))
#define sqr(x) ( (x) * (x) )
#define all(v) v.begin(),  v.end()

typedef pair<int, int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef pair<pii,pii> ppp;



void nonint(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
#define N 200020
int st[4*N],maksl[4*N], maksr[4*N], minsl[4*N], minsr[4*N];

vector<int> vec[N];
int n;
void merge(int v){
	st[v] = st[v<<1] + st[v<<1|1];
	maksr[v] = max(maksr[v<<1], st[v<<1] + maksr[v<<1|1]);
	maksl[v] = max(maksl[v<<1|1], st[v<<1|1] + maksl[v<<1]);
	minsr[v] = min(minsr[v<<1], st[v<<1] + minsr[v<<1|1]);
	minsl[v] = min(minsl[v<<1|1], st[v<<1|1] + minsl[v<<1]);
}

void build(int v, int l, int r){
	if (l==r){
		st[v] = 1;
		maksl[v] = maksr[v] = minsl[v] = minsr[v] = st[v];
		return;
	}
	int m = (l+r)>>1;
	build(v<<1,l,m);
	build(v<<1|1,m+1,r);
	merge(v);
}

void update(int v, int l, int r, int x, int val){
	if (l==r){
		st[v] = val;
		maksl[v] = maksr[v] = minsl[v] = minsr[v] = st[v];
		return;
	}
	int m = (l+r)>>1;
	if (x <= m) update(v<<1,l,m,x,val);
	else update(v<<1|1,m+1,r,x,val);
	merge(v);
//	cout<<v<<" "<<maksl[v]<<" "<<maksr[v]<<"\n";
}

int querysum(int v, int l, int r, int ss, int se){
	if (ss > se) return 0;
	if (l==ss && r==se) return st[v];
	int m = (l+r)>>1;
	return querysum(v<<1,l,m,ss,min(se,m)) + querysum(v<<1|1,m+1,r,max(m+1,ss),se);
}

int querymaksr(int v, int l, int r, int ss, int se){
	if (ss > se) return -1e9;
	if (l == ss && r == se) return maksr[v];
	int m = (l+r)>>1;
	ll res = max(querymaksr(v<<1,l,m,ss,min(m,se)), querysum(1,0,n-1,ss,min(m,se)) + querymaksr(v<<1|1,m+1,r,max(m+1,ss),se));
	return res;
}

int querymaksl(int v, int l, int r, int ss, int se){
	if (ss > se) return -1e9;
	if (l == ss && r == se) return maksl[v];
	int m = (l+r)>>1;
	return max(querysum(1,0,n-1,max(m+1,ss),se) + querymaksl(v<<1,l,m,ss,min(m,se)), querymaksl(v<<1|1,m+1,r,max(m+1,ss),se));	
}

int queryminsr(int v, int l, int r, int ss, int se){
	if (ss > se) return 1e9;
	if (l == ss && r == se) return minsr[v];
	int m = (l+r)>>1;
	return min(queryminsr(v<<1,l,m,ss,min(m,se)), querysum(1,0,n-1,ss,min(m,se)) + queryminsr(v<<1|1,m+1,r,max(m+1,ss),se));
}

int queryminsl(int v, int l, int r, int ss, int se){
	if (ss > se) return 1e9;
	if (l == ss && r == se) return minsl[v];
	int m = (l+r)>>1;
	return min(querysum(1,0,n-1,max(m+1,ss),se) + queryminsl(v<<1,l,m,ss,min(m,se)), queryminsl(v<<1|1,m+1,r,max(m+1,ss),se));
}

ll ans[N];
void solve(){
	cin>>n;
	rep(i,0,n) {
		int x; cin>>x;
		vec[x].pb(i);
	}
	
	build(1,0,n-1);	
	rep(i,1,n+1){
		for(auto j : vec[i]){
			ll ma1 = max(0,querymaksl(1,0,n-1,0,j-1));
			ll ma2 = max(0,querymaksr(1,0,n-1,j+1,n-1));
			ll mk = ma1+ma2+1;			
			ans[j] = max(ans[j], mk/2);
		}				
				
		rep(j,0,vec[i].sz) update(1,0,n-1,vec[i][j],-1);
		
		for(auto j : vec[i]){			
			ll mi1 = min(0,queryminsl(1,0,n-1,0,j-1));
			ll mi2 = min(0,queryminsr(1,0,n-1,j+1,n-1));
			ll mn = -(mi1+mi2)+1;
			ans[j] = max(ans[j], (mn-1)/2);
		}
	}
	rep(i,0,n) cout<<ans[i]<<" ";
	cout<<"\n";
}

int main()
{
	nonint();
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}




