#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define MP make_pair
template <class Miaowu>
inline void in(Miaowu &x){
	char c;x=0;bool f=0;
	for(c=getchar();c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x=f?-x:x;
}
const int N=5e5+5;
ll ans[N],sum[N<<6];
vector<pii>vc[N];
int n,tot,aa[N],a[N],head[N<<6],de[N<<6],bel[N],ds1[N],ds2[N],tag1[N],tag2[N],bg[N],ed[N],sufmn[N];
struct Edge{int to,nxt;}e[N<<6];
inline void addedge(int u,int v){
	e[++tot]=Edge{v,head[u]},head[u]=tot;
}
inline void dfs(int u){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		de[v]=de[u]+1,sum[v]+=sum[u],dfs(v);
	}
}
inline int qry1(int y){
	if(y==1)return 0;
	return tag1[bel[y-1]]+ds1[y-1];
}
inline int qry2(int y){
	if(y==n)return 0;
	return tag2[bel[y+1]]+ds2[y+1];
}
inline void add1(int y,int v){
	for(int i=bel[y]+1;i<=bel[n];i++)tag1[i]+=v;
	for(int i=y;i<=ed[bel[y]];i++)ds1[i]+=v;
}
inline void add2(int y,int v){
	for(int i=1;i<bel[y];i++)tag2[i]+=v;
	for(int i=bg[bel[y]];i<=y;i++)ds2[i]+=v;
}
inline void work(int l,int op){
	for(int i=0;i<=n+1;i++){
		sufmn[i]=2e9;
		tag1[i]=tag2[i]=ds1[i]=ds2[i]=bg[i]=ed[i]=0;
	}
	int B=(int)sqrt(1.0*n);
	for(int i=1;i<=n;i++)bel[i]=(i-1)/B+1,ed[bel[i]]=i;
	for(int i=n;i>=1;i--)bg[bel[i]]=i;
	int ind=tot=0,rt;
	for(int i=1;i<=n;i++){
		ind++,head[ind]=0;
		vc[i].clear();
		vc[i].push_back(MP(a[i],ind));
		add1(a[i],1);
		sufmn[a[i]]=min(sufmn[a[i]],i);
	}
	for(int i=n;i>=1;i--)
		sufmn[i]=min(sufmn[i],sufmn[i+1]);
	int mny=2e9;
	for(int i=n;i>=1;i--){
		if(op==0)ans[i+l-1]-=qry2(a[i])+1,ans[i+l-1]-=(n-1-qry1(a[i])-qry2(a[i]));
		else ans[n-i+l]-=qry2(a[i])+1;
		mny=min(mny,a[i]);
		add2(a[i],1);
		for(int ii=0;ii<vc[i].size();ii++){
			pii x=vc[i][ii];
			sum[x.second]=qry1(x.first);
			if(i==1&&x.first==1)continue;
			int qx=sufmn[x.first],qy=mny;
			if(vc[qx].back().first!=qy){
				ind++,head[ind]=0;
				addedge(ind,x.second);
				if(qx==1&&qy==1)rt=ind;
				vc[qx].push_back(MP(qy,ind));
			}
			else{
				addedge(vc[qx].back().second,x.second);
			}
		}
		add1(a[i],-1);
	}
	dfs(rt);
}
inline void solve(int l,int r){
	int _n=n;n=r-l+1;
	for(int i=1;i<=n;i++)
		a[i]=aa[i+l-1]-l+1;
	work(l,0);
	for(int i=1;i<=n;i++)
		ans[i+l-1]+=n+sum[i];
	reverse(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		a[i]=n-a[i]+1;
	work(l,1);
	for(int i=1;i<=n;i++)
		ans[n-i+l]+=n+sum[i];
	for(int i=1;i<=n;i++)
		a[i]=n-a[i]+1;
	reverse(a+1,a+n+1);
	n=_n;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		in(aa[i]);
	for(int i=1;i<=n;i++){
		int j=i,mx=0,mn=2e9;
		while(j<=n){
			mx=max(mx,aa[j]);
			mn=min(mn,aa[j]);
			if(mn==i&&mx==j){
				break;
			}
			j++;
		}
		solve(i,j),i=j;
	}
	for(int i=1;i<=n;i++)
		printf("%lld ",ans[i]);
	return 0;
}