/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

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

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 19;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int t, n, q[N], p[N], mx[lg][N], ch[2][N];
ll ans[N], now, dp[3][N], subt[N];

int get(int l, int r) {
    int maxi = l;
    for(int i=lg-1; i>=0; i--) {
        if(l+(1<<i)-1 <= r) {
            maxi = (p[maxi]<p[mx[i][l]] ? mx[i][l] : maxi);
            l += (1<<i);
        }
    }
    return maxi;
}

int divide(int l, int r) {
    if(r<l) return 0;
    int mid = get(l, r);
    int lft=divide(l, mid-1), rgt=divide(mid+1, r);
    ch[0][mid] = lft, ch[1][mid] = rgt;
    subt[mid]++; subt[mid]+=subt[lft]; subt[mid]+=subt[rgt];
    // cout<<mid<<" => "<<lft<<' '<<rgt<<endl;
    return mid;
}

void dfs(int v) {
    if(v == 0) return;
    dfs(ch[0][v]); dfs(ch[1][v]);
    dp[0][v] += (dp[2][ch[0][v]]);
    dp[0][v] += (dp[1][ch[1][v]]);

    dp[1][v] = 1ll + subt[ch[1][v]] + dp[1][ch[0][v]] + dp[1][ch[1][v]];
    dp[2][v] = 1ll + subt[ch[0][v]] + dp[2][ch[0][v]] + dp[2][ch[1][v]];
    // cout<<v<<" =====> "<<dp[0][v]<<endl;
}
void dfs2(int v) {
    if(v == 0) return;
    ans[v] = now + (n - subt[v]) + dp[0][v];
    now += dp[1][ch[1][v]];
    dfs2(ch[0][v]);
    now -= dp[1][ch[1][v]];
    now += dp[2][ch[0][v]];
    dfs2(ch[1][v]);
    now -= dp[2][ch[0][v]];
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n;
    for(int i=1; i<=n; i++) cin>>p[i], mx[0][i]=i, q[p[i]]=i;
    for(int i=n; i>=1; i--) {
        for(int j=1; j<lg; j++) {
            int x=mx[j-1][i], y=mx[j-1][min(n,i+(1<<(j-1)))];
            mx[j][i] = (p[x]>p[y] ? x : y);
        }
    }

    divide(1, n);
    dfs(q[n]);
    dfs2(q[n]);

    for(int i=1; i<=n; i++) cout<<ans[i]<<' ';

	return 0;
}