#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;

// @author: pashka
struct segtree {
    typedef pair<int, int> item;

    item zero_sum = {INT_MIN, -1};

    item oper(item a, item b) {
        return max(a, b);
    }

    vector<item> sums;

    int size;

    void set(int i, item x, int n, int L, int R) {
        if (R == L + 1) {
            sums[n] = x;
            return;
        }
        int M = (L + R) >> 1;
        if (i < M) {
            set(i, x, 2 * n + 1, L, M);
        } else {
            set(i, x, 2 * n + 2, M, R);
        }
        sums[n] = oper(sums[2 * n + 1], sums[2 * n + 2]);
    }

    item calc(int l, int r, int n, int L, int R) {
        if (l >= R || L >= r) return zero_sum;
        if (L >= l && R <= r) {
            return sums[n];
        }
        int M = (L + R) >> 1;
        return oper(calc(l, r, 2 * n + 1, L, M),
                   calc(l, r, 2 * n + 2, M, R));
    }

    explicit segtree(int n) {
        size = 1;
        while (size < n) size *= 2;
        sums.assign(2 * size, zero_sum);
    }

    explicit segtree(vector<item> a): segtree(a.size()) {
        int n = a.size();
        for (int i = 0; i < n; i++) {
            sums[size - 1 + i] = a[i];
        }
        for (int i = size - 2; i >= 0; i--) {
            sums[i] = oper(sums[2 * i + 1], sums[2 * i + 2]);
        }
    }

    void set(int i, item x) {
        set(i, x, 0, 0, size);
    }

    item calc(int l, int r) {
        return calc(l, r, 0, 0, size);
    }
};

vector<long> res;

void add_res(int l, int r, long x) {
    res[l] += x;
    res[r] -= x;
}

pair<long, long> go(int l, int r, segtree &st) {
    if (r == l) return {0, 0};
    int x = st.calc(l, r).second;
    auto ll = go(l, x, st);
    auto rr = go(x + 1, r, st);
    add_res(x, x + 1, ll.second + rr.first);

    add_res(l, x, 1 + rr.first + (r - x - 1));
    add_res(x + 1, r, 1 + ll.second + (x - l));

    return {ll.first + 1 + rr.first + (r - x - 1),
            rr.second + 1 + ll.second + (x - l)};
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].first;
        p[i].second = i;
    }
    segtree st(p);

    res.resize(n + 1);
    go(0, n, st);
    for (int i = 1; i <= n; i++) res[i] += res[i - 1];
    for (int i = 0; i< n; i++) cout << res[i] << " ";

    return 0;
}