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

#define sz(s) (int)s.size()
#define f first
#define s second
#define pb push_back
#define all(s) s.begin(), s.end()

#define vi vector<int>
#define vvi vector<vi>

#define ll long long
#define vll vector<ll>

#define ii pair<int, int>
#define vii vector<ii>
#define vvii vector<vii>

const int INF = 1e9 + 7;
const int mod = 1e9 + 7;
const int N = 1e6 + 7;
const int T = 1 << 20;
#define ld long double

int n;

int suma[T + T];
int maxi[T + T];

void set_val(int poz, int val){
    poz += T;
    suma[poz] = val;
    maxi[poz] = max(val, 0);
    poz /= 2;

    while(poz > 0){
        suma[poz] = suma[poz + poz] + suma[poz + poz + 1];
        maxi[poz] = max(maxi[poz + poz + 1], suma[poz + poz + 1] + maxi[poz + poz]);
        poz /= 2;
    }
}

int max_suf(int poz){
    poz += T;
    int ret = 1;
    int temp_suma = 1;

    while(poz > 0){
        if(poz % 2 == 1){
            ret = max(ret, maxi[poz - 1] + temp_suma);
            temp_suma += suma[poz - 1];
        }
        poz /= 2;
    }   
    return ret;
}

vector<int> policz(vector<int> tab){
    for(auto & u : tab)
        assert(u >= 0 and u <= n);

    for(int i = 0; i < T + T; i++)
        suma[i] = maxi[i] = 0;

    for(int i = T; i < T + n; i++)
        suma[i] = maxi[i] = 1;
    for(int i = T - 1; i > 0; i--)
        suma[i] = maxi[i] = suma[i + i] + suma[i + i + 1];

    vector<vector<int> > values(n + 1);

    for(int i = 0; i < n; i++)
        values[tab[i]].pb(i);

    vector<int> ret(n);

    for(int i = 0; i <= n; i++){
        for(auto & poz : values[i])
            ret[poz] = max_suf(poz);
        for(auto & poz : values[i])
            set_val(poz, -1);
    }
    return ret;
}

void solve(){
    cin >> n;

    vector<int> tab(n);
    for(int i = 0; i < n; i++)
        cin >> tab[i];

    // for(auto & u : tab)
    //     cout << u << ' ';
    // cout << endl;

    vector<int> ans(n);

    for(int faza = 0; faza < 2; faza++){
        // cout << "Tab: ";
        // for(auto & u : tab)
            // cout << u << ' ';
        // cout << endl;
        auto a = policz(tab);
        reverse(all(tab));
        auto b = policz(tab);
        reverse(all(b));
        reverse(all(tab));

        // cout << "a : ";
        // for(auto & u : a)
        //     cout << u << ' ';
        // cout << endl;
        // cout << "b : ";
        // for(auto & u : b)
        //     cout << u << ' ';
        // cout << endl;
        
        for(int i = 0; i < n; i++)
            ans[i] = max(ans[i], (a[i] + b[i] - 1 - faza) / 2);
    
        for(auto & u : tab)
            u = -u + n;    
    }

    for(int i = 0; i < n; i++)
        cout << ans[i] << ' ';
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int test = 1;
    // cin >> test;

    for(int i = 0; i < test; i++)
        solve();
}