// Marcin Knapik

#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;

// #define DEBUG

#define FOR(i, n) for (int i = 0; i < n; i++)
#define f first
#define s second
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

template <class T>ostream &operator<<(ostream &os, vector<T> &vec){for (T &el : vec){os << el << ' ';}return os;}
template <class T>istream &operator>>(istream &is, vector<T> &vec) {for (T &el : vec){is >> el;}return is;}

template <class T, class G> ostream &operator<<(ostream &os, pair<T, G> para) { os << para.f << ' ' << para.s; return os;}

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vll = vector<ll>;
using vvpll = vector<vpll>;
using vii = vector<ii>;
using mp = map<vector<string>, long double>;
using ld = long double;

const int N = 200004;
const int T = 1 << 18;

enum kierunek {
    LEWO = 0,
    PRAWO = 1
};
#define L kierunek::LEWO
#define R kierunek::PRAWO

int tree[2][T + T];
void add(kierunek kier, int poz){ // zawsze dodajemy tylko jedynkę
    poz += T;
    while(poz > 0){
        tree[kier][poz]++;
        poz >>= 1;
    }
}

// int ask(kierunek kier, int poz){
//     int ret = 0;
//     if(kier == kierunek::LEWO){
//         // pytam o liczbe wartosci wiekszych lub rownych od poz
//         if(poz <= 0){
//             return tree[kier][1];
//         }

//         poz += T - 1;

//         while(poz > 0){
//             if((poz & 1) == 0){
//                 ret += tree[kierunek::LEWO][poz + 1];
//             }
//             poz >>= 1;
//         }
//     } else {
//         // pytam o liczbe wartosci mniejszych lub rownych
//         if(poz < 0){
//             return 0; 
//         }

//         poz += T + 1;
//         while(poz > 0){
//             if(poz & 1){
//                 ret += tree[kierunek::PRAWO][poz - 1];
//             }
//             poz >>= 1;
//         }
//     }

//     return ret;
// }

int ask(kierunek kier, int pocz, int kon){
    pocz = max(pocz, 0);
    if(kon < pocz){
        return 0;
    }

    if(pocz == kon){
        return tree[kier][pocz + T];
    }

    assert(pocz < T);
    int ret = tree[kier][pocz + T];

    pocz += T;
    kon += T + 1;

    while(pocz >> 1 != kon >> 1){
        if((pocz & 1) ^ 1){
            ret += tree[kier][pocz + 1];
        }
        if(kon & 1){
            ret += tree[kier][kon - 1];
        }
        pocz >>= 1;
        kon >>= 1;
    }

    return ret;
}

int dol_tab[N], gora_tab[N];
int gora_max_pref[N];
int gora_min_suf[N];

int dol_max_pref[N];
int dol_min_suf[N];
ll ans[N];
int n;

unordered_map<ll, ll> mapa_req[2];
vector<pair<int, ii> > requests[2];
unordered_map<ll, int> requests_prep[2];

ll haszuj(int gora, int dol){
    return ((1ll * (gora + 5)) << 30) + (dol + 5);
}

ll haszuj(int a, ii bc){
    return (1ll * (a + 3) << 40) + (1ll * (bc.f + 3) << 20) + bc.s;  
}

int ile_przecina(int gora, int dol){
    return requests_prep[kierunek::PRAWO][haszuj(gora + 1, {0, dol - 1})] + 
           requests_prep[kierunek::LEWO][haszuj(gora - 1, {dol + 1, n - 1})];
}

ii nowa_gora_nowy_dol(kierunek kier, int gora, int dol){
    if(kier == kierunek::PRAWO) { // prawa strona rekurencji
        return {dol_max_pref[dol + 1], gora_max_pref[gora + 1]};
    } else {
        return {dol_min_suf[dol], gora_min_suf[gora]};
    }
}


// ponizsza funkcje jest tylko po to, żebyśmy mogli zrobić zapytania o przedzialy offline
void req_dummy(int gora, int dol, kierunek kier){
#ifdef DEBUG
    cout << "DUMMY REQ: " << gora << ' ' << dol << ' ' << kier << ' ' << endl;
#endif

    ll hasz = haszuj(gora, dol);
    
    if(mapa_req[kier].count(hasz)){
        return;
    }
    mapa_req[kier][hasz] = -1;

    auto [nowa_gora, nowy_dol] = nowa_gora_nowy_dol(kier, gora, dol);

    if(nowa_gora == gora and dol == nowy_dol){
        return;
    }

    // ile jest w odleglosci 2 'polknietych' przez kolejne maxy
    if(nowa_gora != gora and nowy_dol != dol){
        if(kier == kierunek::PRAWO){
            requests[kierunek::LEWO].pb({gora, {dol + 1, nowy_dol - 1}});
            requests[kierunek::LEWO].pb({nowa_gora - 1, {dol + 1, nowy_dol - 1}});
        } else {
            requests[kierunek::PRAWO].pb({gora, {nowy_dol + 1, dol - 1}});
            requests[kierunek::PRAWO].pb({nowa_gora + 1, {nowy_dol + 1, dol - 1}});
        }
    }

    // krawedzie_tab przecinajace sie aktualnym horyzontem
    requests[kierunek::LEWO].pb({gora - 1, {dol + 1, n - 1}});
    requests[kierunek::PRAWO].pb({gora + 1, {0, dol - 1}});

    req_dummy(nowa_gora, nowy_dol, kier);
}

ll req(int gora, int dol, kierunek kier, int ile_zostalo){
#ifdef DEBUG
    cout << "REQ: " << gora << ' ' << dol << "  KIER: " << kier << "  ILE ZOSTALO: " << ile_zostalo << endl;
#endif

    ll hasz = haszuj(gora, dol);
    auto it = mapa_req[kier].find(hasz);
    assert(it != mapa_req[kier].end());

    if(it -> second != -1){
#ifdef DEBUG
        cerr << "MAM SPAMIENTANE " << it -> second << endl; 
#endif
        return it -> second;
    }

    auto [nowa_gora, nowy_dol] = nowa_gora_nowy_dol(kier, gora, dol);
    if(nowa_gora == gora and dol == nowy_dol){
        assert(ile_zostalo == 0);
        return mapa_req[kier][hasz] = 0;
    }

    ll ret = ile_zostalo;
    int ile_2 = 0;
    // ile jest w odleglosci 2 'polknietych' przez kolejne maxy
    if(nowa_gora != gora and nowy_dol != dol){
        if(kier == kierunek::PRAWO){
            ile_2 = requests_prep[L][haszuj(nowa_gora - 1, {dol + 1, nowy_dol - 1})] - 
                    requests_prep[L][haszuj(gora, {dol + 1, nowy_dol - 1})];
        } else {
            ile_2 = requests_prep[R][haszuj(nowa_gora + 1, {nowy_dol + 1, dol - 1})] -
                    requests_prep[R][haszuj(gora, {nowy_dol + 1, dol - 1})];
        }
    }

#ifdef DEBUG
    cout << "NOWA GORA  " << nowa_gora << ' ' << "NOWY DOL " << nowy_dol << endl;
    cout << "ILE PRZECINA " << ile_przecina(gora, dol) << ' ' << " ILE2: " << ile_2 << endl;
#endif

    return mapa_req[kier][hasz] = ret +
                                  ile_2 +
                                  req(nowa_gora,
                                      nowy_dol,
                                      kier,
                                      ile_zostalo - ile_przecina(gora, dol) - ile_2);
}

void solve(int pocz, int kon){
    // pocz i kon to zakres jednej spójnej składowej
    
    for(int i = pocz; i <= kon; i++){
        int pom = ile_przecina(i, gora_tab[i]);
        ans[i] = req(i, gora_tab[i], kierunek::PRAWO, ((kon - i) + (kon - gora_tab[i]) + pom) / 2) +
                 req(i, gora_tab[i], kierunek::LEWO, ((i - pocz) + (gora_tab[i] - pocz) + pom) / 2) -
                 ile_przecina(i, gora_tab[i]); 
#ifdef DEBUG
        cout << "WYLICZYŁ ANS " << ans[i] << endl << endl;
#endif
    }
}

void solve(){
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> gora_tab[i];
        gora_tab[i]--;

        dol_tab[gora_tab[i]] = i;
    }

    gora_max_pref[0] = -1;
    dol_max_pref[0] = -1;

    for(int i = 0; i < n; i++){
        gora_max_pref[i + 1] = max(gora_max_pref[i], gora_tab[i]);
        dol_max_pref[i + 1] = max(dol_max_pref[i], dol_tab[i]);
    }

    gora_min_suf[n] = n;
    dol_min_suf[n] = n;

    for(int i = n - 1; i >= 0; i--){
        gora_min_suf[i] = min(gora_min_suf[i + 1], gora_tab[i]);
        dol_min_suf[i] = min(dol_min_suf[i + 1], dol_tab[i]);
    }

    FOR(i, n){
        req_dummy(i, gora_tab[i], kierunek::PRAWO);
        req_dummy(i, gora_tab[i], kierunek::LEWO);
    }
    // exit(0);

    // offline preprocesing 
    // już tutaj mozna sprawdzic, czy nie dostaniemy tle (przez za dużo wywolan req)
    // lewa strona

    sort(all(requests[L]));
    requests[L].resize(unique(all(requests[L])) - requests[L].begin());
    int last = -1;
    for(auto & [gora, dol] : requests[L]){
        while(last < gora){
            last++;
            add(L, gora_tab[last]);
        }
        requests_prep[L][haszuj(gora, dol)] = ask(kierunek::LEWO, dol.f, dol.s);
    }

    sort(requests[R].rbegin(), requests[R].rend());
    last = n;
    for(auto & [gora, dol] : requests[R]){
        while(last > gora){
            last--;
            add(R, gora_tab[last]);
        }
        requests_prep[R][haszuj(gora, dol)] = ask(kierunek::PRAWO, dol.f, dol.s);
    }

    // int tot = sz(mapa_req[kierunek::LEWO]) + sz(mapa_req[kierunek::PRAWO]);
    // cerr << n << " -> " << tot << ' ' << setprecision(2) << fixed << "    " << (tot/(ld)n) << endl;

    // JAZDA!

    int start = 0;
    for(int i = 0; i < n; i++) {
        if(gora_max_pref[i + 1] == i) {
            assert(dol_max_pref[i + 1] == i);
            solve(start, i);
            start = i + 1;
        }
    }

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

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

    int tests = 1;
    // cin >> tests;

    for (int test = 1; test <= tests; test++) {
        solve();
    }

    return 0;
}