#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 300100;

int n, a[maxn], b[maxn], stk[maxn], top, L[maxn], R[maxn];
ll f[maxn], g[maxn], sz[maxn];
vector<int> G[maxn];

void dfs(int u) {
	sz[u] = 1;
	for (int v : G[u]) {
		dfs(v);
		sz[u] += sz[v];
	}
}

void dfs2(int u) {
	for (int v : G[u]) {
		dfs2(v);
		sz[u] += sz[v];
	}
}

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		b[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		while (top && a[stk[top]] < a[i]) {
			--top;
		}
		L[i] = (top ? stk[top] : 1);
		stk[++top] = i;
	}
	top = 0;
	for (int i = n; i; --i) {
		while (top && a[stk[top]] < a[i]) {
			--top;
		}
		R[i] = (top ? stk[top] : n);
		stk[++top] = i;
	}
	for (int i = 2; i <= n; ++i) {
		G[L[i]].pb(i);
	}
	dfs(1);
	dfs2(1);
	for (int i = 1; i <= n; ++i) {
		f[L[i]] += sz[i];
		f[i] -= sz[i];
	}
	for (int i = 1; i <= n; ++i) {
		f[i] += f[i - 1];
		vector<int>().swap(G[i]);
	}
	for (int i = 1; i < n; ++i) {
		G[R[i]].pb(i);
	}
	dfs(n);
	dfs2(n);
	for (int i = 1; i <= n; ++i) {
		g[R[i]] += sz[i];
		g[i] -= sz[i];
	}
	for (int i = n; i; --i) {
		g[i] += g[i + 1];
	}
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", f[i] + g[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}