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

const int maxn = 300010, maxlg = 20;
int lg[maxn], st[maxlg][maxn];
int pre[maxn], nxt[maxn];
int p[maxn], rev[maxn], n;
void solve(int, int);
long long ans[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", p + i), rev[p[i]] = i, st[0][i] = p[i];
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int l = 1; l <= lg[n]; l++)
        for (int i = 1; i + (1 << l) - 1 <= n; i++)
            st[l][i] = max(st[l - 1][i], st[l - 1][i + (1 << (l - 1))]);
    for (int i = 1; i <= n; i++) {
        if (p[i - 1] > p[i]) {
            pre[i] = i - 1;
            continue;
        }
        pre[i] = pre[i - 1];
        while (pre[i] && p[pre[i]] < p[i]) pre[i]--;
    }
    nxt[n + 1] = n + 1;
    for (int i = n; i; i--) {
        if (p[i + 1] > p[i]) {
            nxt[i] = i + 1;
            continue;
        }
        nxt[i] = nxt[i + 1];
        while (nxt[i] != n + 1 && p[nxt[i]] < p[i]) nxt[i]++;
    }
    solve(1, n);
    for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
    printf("\n");
    return 0;
}

long long c(int l, int r) {
    static unordered_map<long long, long long> mp;
    if (l > r)
        return 0;
    if (l == r)
        return 1;
    long long I = 1ll * l * (n + 1) + r;
    if (mp[I])
        return mp[I];
    if (nxt[l] < r)
        return mp[I] = c(l, nxt[l]) + c(nxt[l], r) - 1;
    if (pre[r] > l)
        return mp[I] = c(l, pre[r]) + c(pre[r], r) - 1;
    return mp[I] = c(l + 1, r - 1) + r - l + 1;
}

long long cL(int l) {
    static unordered_map<int, long long> mp;
    if (l > n)
        return 0;
    if (mp[l])
        return mp[l];
    if (nxt[l] == n + 1)
        return mp[l] = cL(l + 1) + n - l + 1;
    return mp[l] = c(l + 1, nxt[l] - 1) + cL(nxt[l]) + nxt[l] - l;
}

long long cR(int r) {
    static unordered_map<int, long long> mp;
    if (!r)
        return 0;
    if (mp[r])
        return mp[r];
    if (pre[r] == 0)
        return mp[r] = cR(r - 1) + r;
    return mp[r] = c(pre[r] + 1, r - 1) + cR(pre[r]) + r - pre[r];
}

int rmq(int l, int r) {
    int Lg = lg[r - l + 1];
    return max(st[Lg][l], st[Lg][r - (1 << Lg) + 1]);
}

void s(int l, int r) {
    if (l > r)
        return;
    int mx = rmq(l, r), p = rev[mx];
    auto L = c(p, r + 1) - 1, R = c(l - 1, p) - 1;
    ans[l] += L, ans[p] -= L, ans[p + 1] += R, ans[r + 1] -= R;
    auto x = c(l - 1, p - 1) + c(p + 1, r + 1) - 2;
    ans[p] += x, ans[p + 1] -= x;
    s(l, p - 1), s(p + 1, r);
    return;
}

void sL(int r) {
    if (!r)
        return;
    int mx = rmq(1, r), p = rev[mx];
    auto L = c(p, r + 1) - 1, R = cR(p);
    ans[1] += L, ans[p] -= L, ans[p + 1] += R, ans[r + 1] -= R;
    auto x = cR(p - 1) + c(p + 1, r + 1) - 1;
    ans[p] += x, ans[p + 1] -= x;
    sL(p - 1), s(p + 1, r);
    return;
}

void sR(int l) {
    if (l == n + 1)
        return;
    int mx = rmq(l, n), p = rev[mx];
    auto L = cL(p), R = c(l - 1, p) - 1;
    ans[l] += L, ans[p] -= L, ans[p + 1] += R, ans[n + 1] -= R;
    auto x = cL(p + 1) + c(l - 1, p - 1) - 1;
    ans[p] += x, ans[p + 1] -= x;
    s(l, p - 1), sR(p + 1);
    return;
}

void solve(int l, int r) {
    int mx = rmq(l, r), p = rev[mx];
    auto L = cL(p), R = cR(p);
    ans[1] += L, ans[p] -= L, ans[p + 1] += R, ans[n + 1] -= R;
    auto x = cR(p - 1) + cL(p + 1);
    ans[p] += x, ans[p + 1] -= x;
    sL(p - 1), sR(p + 1);
    for (int i = 1; i <= n; i++) ans[i] += ans[i - 1];
    return;
}