#include <bits/stdc++.h>

#define f first
#define s second
#define endl '\n'
#define vec vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define m_p make_pair
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)

using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

auto rng=bind(uniform_int_distribution<int>(0,25),mt19937(time(0)));

template<class T>bool umin(T &a,const T &b) {return (a>b?a=b,1:0);}
template<class T>bool umax(T &a,const T &b) {return (a<b?a=b,1:0);}

//set<pii>st1,st2;
/// who,dp,size
//#define int long long
typedef long double ld;
const int inf=1e9;
const int N=2e5+5;
struct tree{
    int t[4*N],p[4*N];
    void init(){
        fill(t,t+4*N,0);
        fill(p,p+4*N,0);
    }
    void push(int v,int tl,int tr){
        if(tl==tr || !p[v]) return;
        t[2*v]+=p[v];
        t[2*v+1]+=p[v];
        p[2*v]+=p[v];
        p[2*v+1]+=p[v];
        p[v]=0;
    }
    void add(int l,int r,int x,int v,int tl,int tr){
        if(tl>=l && tr<=r){
            t[v]+=x;
            p[v]+=x;
            return ;
        }
        if(tl>r || tr<l) return;
        push(v,tl,tr);
        int tm=(tl+tr)/2;
        add(l,r,x,2*v,tl,tm);
        add(l,r,x,2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
    int get(int l,int r,int v,int tl,int tr){
        if(tl>=l && tr<=r){
            return t[v];
        }
        if(tl>r || tr<l) return -inf;
        push(v,tl,tr);
        int tm=(tl+tr)/2;
        return max(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
    }
}T1[2],T2[2];
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vec<int>a(n);
    for(auto &z : a)
        cin>>z;
//    vec<int>ans(n,0);
    auto solve=[&](int add){
        vec<vec<int>>ids(n+1,vec<int>());
        for(int i=0;i<2;i++) T1[i].init(),T2[i].init();
        for(int i=0;i<n;i++){
            ids[a[i]].pb(i);
        }
        for(int i=0;i<=n;i++){
            T1[i%2].add(i,i,i,1,0,n);
            T1[1-(i%2)].add(i,i,-inf,1,0,n);
            T2[i%2].add(i,i,-i,1,0,n);
            T2[1-(i%2)].add(i,i,-inf,1,0,n);
        }
        vec<int>mys(n,0);
        for(int x=0;x<=n;x++){
//            vec<int>m1(2,-inf);
//            vec<int>m2(2,-inf);
            for(auto &i : ids[x]){
                T2[0].add(i+1,n,2,1,0,n);
                T2[1].add(i+1,n,2,1,0,n);
                T1[0].add(i+1,n,-2,1,0,n);
                T1[1].add(i+1,n,-2,1,0,n);
            }
            for(auto &i : ids[x]){
//                T1[0].add(i+1,n,-2,1,0,n);
//                T1[1].add(i+1,n,-2,1,0,n);
//                mys[i]=mx;
                for(int j=0;j<2;j++){
                    for(int k=0;k<2;k++){
                        int w=T2[j].get(i+1,n,1,0,n)+T1[k].get(0,i,1,0,n);
                        w--;w/=2;
                        if(j==k) w+=add;
                        umax(mys[i],w);
                    }
                }
            }
        }
        return mys;
    };
    vec<int>f1=solve(-1);
    reverse(all(a));for(auto &z : a) z=n-z+1;
    vec<int>f2=solve(1);reverse(all(f2));
//    vec<int>f4=solve(1,-1);reverse(all(f4));

//    for()
    for(int i=0;i<n;i++){
//        cerr<<f1[i]<<' ';
        cout<<max({f1[i],f2[i]})<<' ';
    }
    return  0;
}
/*
12 1
1 1 2 2 3 3 4 8 8 6 3
*/
