#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define pi pair<int,int> #define m_p make_pair #define p1 first #define p2 second using namespace std; typedef long long ll; const int V=5e5; const int maxn=1e6+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,a[maxn],sufmx[maxn],sufmn[maxn],S[maxn],tp; ll d[maxn]; struct ST { int t[maxn][20],Log_2[maxn]; void init(){ up(i,2,n)Log_2[i]=Log_2[i>>1]+1; up(i,1,n)t[i][0]=a[i]; up(i,1,Log_2[n])up(j,1,n-(1<<i)+1)t[j][i]=max(t[j][i-1],t[j+(1<<i-1)][i-1]); }int qry(int l,int r){ int k=Log_2[r-l+1]; return max(t[l][k],t[r-(1<<k)+1][k]); } }T; struct ST2 { int t[maxn][20],Log_2[maxn]; void init(){ up(i,2,n)Log_2[i]=Log_2[i>>1]+1; up(i,1,n)t[i][0]=a[i]; up(i,1,Log_2[n])up(j,1,n-(1<<i)+1)t[j][i]=min(t[j][i-1],t[j+(1<<i-1)][i-1]); }int qry(int l,int r){ int k=Log_2[r-l+1]; return min(t[l][k],t[r-(1<<k)+1][k]); } }T2; void slv(){ n=read();up(i,1,n)a[i]=read();T.init(),T2.init(); S[tp=0]=n+1; down(i,n,1){ while(tp&&a[S[tp]]<=a[i])tp--; sufmx[i]=S[tp],S[++tp]=i; }S[tp=0]=n+1; down(i,n,1){ while(tp&&a[S[tp]]>=a[i])tp--; sufmn[i]=S[tp],S[++tp]=i; } up(i,1,n){ vector<int>v; int x=i,y=i; while(x!=n+1)v.p_b(x),x=sufmx[x]; while(y!=n+1)v.p_b(y),y=sufmn[y]; v.p_b(n+1); sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); up(j,1,int(v.size())-1){ int x=T.qry(i,v[j-1]),y=T2.qry(i,v[j-1]); d[v[j-1]-i+1]+=x*y; d[v[j]-i+1]-=x*y; } } up(i,1,n)d[i]+=d[i-1]; up(i,1,n)printf("%lld ",d[i]); } int main(){ slv(); return 0; }