#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], dp[5][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];
    for(int i=0; i<5; i++) dp[i][now]=1;
    if(L[now]!=-1)
    {
        dfs2(L[now]);
        dp[0][now]+=dp[1][L[now]];
        dp[1][now]+=dp[1][L[now]];
        dp[2][now]+=dp[0][L[now]]+sz[L[now]];
        dp[3][now]+=dp[1][L[now]];
        dp[4][now]+=dp[4][L[now]]+sz[L[now]];
        ls=sz[L[now]];
        if(l!=1) lv=dp[2][L[now]];
        else lv=dp[4][L[now]];
    }
    if(R[now]!=-1)
    {
        dfs2(R[now]); 
        dp[0][now]+=dp[2][R[now]];
        dp[1][now]+=dp[0][R[now]]+sz[R[now]];
        dp[2][now]+=dp[2][R[now]];
        dp[3][now]+=dp[3][R[now]]+sz[R[now]];
        dp[4][now]+=dp[2][R[now]];
        rs=sz[R[now]];
        if(r!=N) rv=dp[1][R[now]];
        else rv=dp[3][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");
}