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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, A[MAXN+10];

struct SEG
{
    pii tree[MAXN*4+10];
    void init(int node, int tl, int tr)
    {
        if(tl==tr)
        {
            tree[node]=pii(A[tl], tl);
            return;
        }
        int mid=tl+tr>>1;
        init(node*2, tl, mid);
        init(node*2+1, mid+1, tr);
        tree[node]=max(tree[node*2], tree[node*2+1]);
    }
    pii query(int node, int tl, int tr, int l, int r)
    {
        if(l<=tl && tr<=r) return tree[node];
        if(r<tl || tr<l) return pii(0, 0);
        int mid=tl+tr>>1;
        return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
    }
}seg;

ll ans[MAXN+10], dp1[MAXN+10], dp2[MAXN+10];
int L[MAXN+10], R[MAXN+10], sz[MAXN+10], root;
pii P[MAXN+10];

int dfs(int l, int r)
{
    if(l>r) return -1;
    int t=seg.query(1, 1, N, l, r).second;
    L[t]=dfs(l, t-1);
    R[t]=dfs(t+1, r);
    sz[t]=r-l+1;
    P[t]={l, r};
    return t;
}

void dfs2(int now)
{
    ll lv=0, rv=0, ls=0, rs=0;
    auto [l, r] = P[now];
    if(L[now]!=-1)
    {
        dfs2(L[now]);
        dp1[now]+=sz[L[now]]+dp1[L[now]];
        dp2[now]+=dp2[L[now]];
        lv=sz[L[now]]+dp1[L[now]];
        if(l!=1) lv=min(lv, sz[L[now]]+dp2[L[now]]);
        ls=sz[L[now]];
    }
    if(R[now]!=-1)
    {
        dfs2(R[now]); 
        dp1[now]+=dp1[R[now]];
        dp2[now]+=sz[R[now]]+dp2[R[now]];
        rv=sz[R[now]]+dp2[R[now]];
        if(r!=N) rv=min(rv, sz[R[now]]+dp1[R[now]]);
        rs=sz[R[now]];
    }
    ans[now]+=lv+rv;
    ans[now+1]-=lv+rv;
    ans[l]+=rv+rs+1;
    ans[now]-=rv+rs+1;
    ans[now+1]+=lv+ls+1;
    ans[r+1]-=lv+ls+1;
}

int main()
{
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d", &A[i]);

    seg.init(1, 1, N);
    root=dfs(1, N);
    dfs2(root);
    for(int i=1; i<=N; i++) ans[i]+=ans[i-1];
    for(int i=1; i<=N; i++) printf("%lld ", ans[i]);
    printf("\n");
}