#include <bits/stdc++.h>
#define ll int
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 500100
#define par pair<ll, ll>
#define ld long double
#define mod 1000000007
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;cin >> n;
    
    vc<ll> a(n);loop(i, 0, n) cin >> a[i];
    function<vc<ll> (vc<ll>)> calc=[&](vc<ll> arr){
        vc<ll> ind(n);loop(i, 0, n) ind[i]=i;
        sort(all(ind), [&](ll x, ll y){
            if(arr[x]==arr[y]) return x>y;
            return arr[x]<arr[y];
        });
        
        vc<ll> tr(4 * n), upd(4 * n, 0);
        function<void (ll, ll, ll)> build=[&](ll l, ll r, ll no){
            if(l+1==r) tr[no]=r;
            else{
                ll mid=(l+r)/2;
                build(l, mid, no * 2);
                build(mid, r, no * 2 + 1);
                tr[no]=min(tr[no * 2], tr[no * 2 + 1]);
            }
        };
        function<ll (ll)> getval=[&](ll no){return tr[no] + upd[no];};
        function<void (ll, ll, ll, ll, ll, ll)> update=[&](ll ql, ll qr, ll val, ll l, ll r, ll no){
            if(ql==l and qr==r) upd[no]+=val;
            else{
                ll mid=(l+r)/2;
                if(qr<=mid) update(ql, qr, val, l, mid, no * 2);
                else if(mid<=ql) update(ql, qr, val, mid, r, no * 2 + 1);
                else update(ql, mid, val, l, mid, no * 2), update(mid, qr, val, mid, r, no * 2 + 1);
                tr[no]=min(getval(no * 2), getval(no * 2 + 1));
                
            }
        };
        function<ll (ll, ll, ll, ll, ll)> query=[&](ll ql, ll qr, ll l, ll r, ll no){
            if(ql==l and qr==r) return getval(no);
            else{
                ll mid=(l+r)/2;
                if(qr<=mid) return upd[no] + query(ql, qr,  l, mid, no * 2);
                else if(mid<=ql) return upd[no] + query(ql, qr,  mid, r, no * 2 + 1);
                else return upd[no] + min(query(ql, mid, l, mid, no * 2), query(mid, qr, mid, r, no * 2 + 1));
            }
        };
        
        build(0, n, 1);
        
        vc<ll> ans(n);
        fore(i, ind){
            ans[i]=query(i, i+1, 0, n, 1)-1-min((ll) 0, query(0, i+1, 0, n, 1));
            update(i, n, -2, 0, n, 1);
        }
        
        return ans;
    };
    //fore (v, calc(a)) cout << v << " ";cout << endl;
    
    vc<ll> mi1=calc(a);reverse(all(a));vc<ll> mi2=calc(a);reverse(all(mi2));
    
    //loop(i, 0, n) cout <<mi1[i]<<" ";cout << endl;
    //loop(i, 0, n) cout << mi2[i]<<" ";cout << endl;
    
    loop(i, 0, n) a[i]=-a[i];
    vc<ll> ma2=calc(a);reverse(all(ma2));reverse(all(a));vc<ll> ma1=calc(a);
    
    vc<ll> ans(n, 0);
    loop(i, 0, n) ans[i]=max((mi1[i]+mi2[i]+1)/2, (ma1[i] + ma2[i])/2);
    loop(i, 0, n) cout << ans[i] <<" ";cout << endl;
}