#include<bits/stdc++.h>
#define ll long long

const int maxn=1e6+5;

int n,a[maxn],rt,x,y,z,pl,pr;
ll sum;
struct node{
    ll val,sum;int l,r,siz;
    node(ll _val=0,ll _sum=0,int _l=0,int _r=0):val(_val),sum(_sum),l(_l),r(_r),siz(_r-_l+1){}
};
std::vector<node>st;
std::vector<std::pair<node,int>>pre,suf;
std::mt19937 rnd(time(0));
node operator +(const node &x,const node &y){return node(x.val+y.val+x.sum*y.siz,x.sum+y.sum,std::min(x.l,y.l),std::max(x.r,y.r));}
bool operator <(const node &x,const node &y){return x.sum*y.siz==y.sum*x.siz?x.l<y.l:x.sum*y.siz<y.sum*x.siz;}
bool operator ==(const node &x,const node &y){return x.val==y.val&&x.sum==y.sum&&x.l==y.l&&x.r==y.r;}
bool operator <=(const node &x,const node &y){return x<y||x==y;}
struct fhq{
    int ls[maxn],rs[maxn],len[maxn],siz[maxn],key[maxn],cnt;
    ll ans[maxn],sum[maxn];
    node val[maxn];
    int newnode(node v){
        val[++cnt]=v;key[cnt]=rnd();siz[cnt]=1;sum[cnt]=v.sum;len[cnt]=v.siz;ans[cnt]=v.val;
        return cnt;
    }
    void push_up(int now){
        siz[now]=siz[ls[now]]+siz[rs[now]]+1;
        len[now]=len[ls[now]]+len[rs[now]]+val[now].siz;
        sum[now]=sum[ls[now]]+sum[rs[now]]+val[now].sum;
        ans[now]=ans[ls[now]]+ans[rs[now]]+val[now].val+(val[now].siz+len[rs[now]])*sum[ls[now]]+val[now].sum*len[rs[now]];
    }
    void split(int now,node k,int &x,int &y){
        if(!now)x=y=0;
        else{
            if(val[now]<=k){
                x=now;
                split(rs[x],k,rs[x],y);
            }else{
                y=now;
                split(ls[y],k,x,ls[y]);
            }
            push_up(now);
        }
    }
    void splitsiz(int now,int k,int &x,int &y){
        if(!now)x=y=0;
        else{
            if(siz[ls[now]]<k){
                x=now;
                splitsiz(rs[x],k-siz[ls[now]]-1,rs[x],y);
            }else{
                y=now;
                splitsiz(ls[y],k,x,ls[y]);
            }
            push_up(now);
        }
    }
    int merge(int x,int y){
        if(!x||!y)return x+y;
        if(key[y]>key[y]){
            rs[x]=merge(rs[x],y);
            push_up(x);
            return x;
        }else{
            ls[y]=merge(x,ls[y]);
            push_up(y);
            return y;
        }
    }
    void insert(int v){
        x=y=0;
        split(rt,val[v],x,y);
        rt=merge(merge(x,v),y);
    }
    void del(node v){
        x=y=z=0;
        split(rt,v,x,z);splitsiz(x,siz[x]-1,x,y);rt=merge(x,z);
    }
}T;

signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)sum=sum+a[i];
    for(int i=1;i<=n;i++){
        node now(a[i],a[i],i,i);
        while(!st.empty()&&st.back()<=now){
            node tmp=st.back();st.pop_back();
            pre.push_back({tmp,-1});now=now+tmp;
        }
        st.push_back(now);pre.push_back({now,1});
    }st.clear();
    for(int i=n;i>=1;i--){
        node now(a[i],a[i],i,i);
        while(!st.empty()&&st.back()<=now){
            node tmp=st.back();st.pop_back();
            suf.push_back({tmp,-1});now=now+tmp;
        }
        st.push_back(now);suf.push_back({now,1});
    }
    for(auto i:st)T.insert(T.newnode(i));
    pl=-1,pr=(int)suf.size()-1;
    for(int i=1;i<=n;i++){
        while(pr>=0&&(suf[pr].first.l!=i+1||suf[pr].second==-1)){
            if(suf[pr].second==1)T.del(suf[pr].first);
            else T.insert(T.newnode(suf[pr].first));
            pr--;
        }
        printf("%lld ",T.ans[rt]+1ll*a[i]*n-sum);
        while(pl==-1||pre[pl].first.r!=i){
            pl++;
            if(pre[pl].second==1)T.insert(T.newnode(pre[pl].first));
            else T.del(pre[pl].first);
        }
    }
    return 0;
}