#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=3e5+5,M=(1<<15)+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,p[N],st[N],sh,L[N],R[N],l[N],r[N];ll f[N][2],ans[N];
void Do(int a,int b){
	int op=(a<b);
	f[a][op]=abs(b-a)-1;
	if(b!=n+1){
		int p=(b>a?r[a]:l[a]);
		if(!b) f[a][op]+=f[p][0];if(p) p=r[p];
		while(p) f[a][op]+=f[p][0],p=r[p];
	}
	if(b!=0){
		int p=(b>a?r[a]:l[a]);
		if(b==n+1) f[a][op]+=f[p][1];if(p) p=l[p];
		while(p) f[a][op]+=f[p][1],p=l[p];
	}
}
void dfs(int x){
	if(!x) return;dfs(l[x]);dfs(r[x]);
	Do(x,L[x]);Do(x,R[x]);
}
void Solve(){
	int i,j;scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&p[i]);
	for(i=1;i<=n;i++){
		while(sh&&p[st[sh]]<p[i]) R[st[sh--]]=i;
		L[i]=st[sh];st[++sh]=i;
	}
	while(sh) R[st[sh--]]=n+1;
	for(i=1;i<=n;i++){
		while(sh&&p[st[sh]]<p[i]) sh--;
		l[i]=r[st[sh]];r[st[sh]]=i;st[++sh]=i;
	}
	dfs(r[0]);
	/*vector<pii> E;
	for(i=1;i<=n;i++) E.emplace_back(i,L[i]),E.emplace_back(i,R[i]);
	sort(E.begin(),E.end(),[](pii x,pii y){return p[x.fi]<p[y.fi];});
	for(auto i:E){
		int op=(i.fi<i.se);
		int x=min(i.fi,i.se),y=max(i.fi,i.se);
		f[i.fi][op]=y-x-1;
		if(i.se!=n+1){
			sh=0;
			for(int j=x+1;j<y;j++) {
				while(sh&&p[st[sh]]<p[j]) sh--;
				st[++sh]=j;
			}
			for(j=1+(i.se!=0);j<=sh;j++) f[i.fi][op]+=f[st[j]][0];
		}
		if(i.se!=0){
			sh=0;
			for(int j=y-1;j>x;j--){
				while(sh&&p[st[sh]]<p[j]) sh--;
				st[++sh]=j;
			}
			for(j=1+(i.se!=n+1);j<=sh;j++) f[i.fi][op]+=f[st[j]][1];
		}
	}*/
	ll tot=0;sh=0;
	for(i=1;i<=n;i++){
		ans[i]+=tot;
		while(sh&&p[st[sh]]<p[i]) tot-=f[st[sh--]][0];
		st[++sh]=i;tot+=f[i][0];
	}
	tot=0;sh=0;
	for(i=n;i;i--){
		ans[i]+=tot;
		while(sh&&p[st[sh]]<p[i]) tot-=f[st[sh--]][1];
		st[++sh]=i;tot+=f[i][1];
	}
	for(i=1;i<=n;i++) printf("%lld ",ans[i]+n-1);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}