#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 210000;

int n;
int p[maxn];

int fa[maxn],li[maxn],ri[maxn],v[maxn];
int findfa(const int x){ return fa[x]==x?x:fa[x]=findfa(fa[x]); }

int minsum[maxn],lsum[maxn],rsum[maxn],lnum[maxn],num[maxn],rnum[maxn];
int ans[maxn];

void add(int l,int r,int c)
{
	ans[l]+=c;
	ans[r+1]-=c;
}

signed main()
{
	///////////////////////////////////////////////
	ios_base::sync_with_stdio(false);
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x; cin>>x;
		p[x]=i;
	}
	
	for(int i=1;i<=n;i++)
	{
		int j=p[i]; 
		fa[j]=j; v[j]=1;
		
		int lf= v[j-1]?findfa(j-1):0;
		int rf= v[j+1]?findfa(j+1):0;
		
		if(lf&&rf)
		{
			if(ri[rf]<n) add(li[lf],ri[lf],minsum[rf]+ri[rf]-li[rf]+1);
			else add(li[lf],ri[lf],lsum[rf]+ri[rf]-li[rf]+1);
			
			if(li[lf]>1) add(li[rf],ri[rf],minsum[lf]+ri[lf]-li[lf]+1);
			else add(li[rf],ri[rf],rsum[lf]+ri[lf]-li[lf]+1);
		}
		if(lf) add(li[lf],ri[lf],1);
		if(rf) add(li[rf],ri[rf],1);
		
		if(lf)
		{
			if(li[lf]>1) add(j,j,minsum[lf]+lnum[lf]);
			else add(j,j,rsum[lf]);
		}
		if(rf)
		{
			if(ri[rf]<n) add(j,j,minsum[rf]+rnum[rf]);
			else add(j,j,lsum[rf]);
		}
		
		li[j]=ri[j]=j;
		minsum[j]=lsum[j]=rsum[j]=1;
		lnum[j]=rnum[j]=0;
		num[j]=1;
		if(lf)
		{
			fa[lf]=j,li[j]=li[lf];
			minsum[j]+= minsum[lf]+rnum[lf];
			lsum[j]+=lsum[lf];
			rsum[j]+=ri[lf]-li[lf]+1+rsum[lf];
			lnum[j]+=lnum[lf]+num[lf];
			num[j]+=rnum[lf];
		}
		if(rf)
		{
			fa[rf]=j,ri[j]=ri[rf];
			minsum[j]+= minsum[rf]+lnum[rf];
			lsum[j]+= ri[rf]-li[rf]+1+lsum[rf];
			rsum[j]+=rsum[rf];
			rnum[j]+=rnum[rf]+num[rf];
			num[j]+=lnum[rf];
		}
	}
	
	for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
	for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
	
	return 0;
}