#include <iostream>

#include <cstdio>

#include <vector>

#include <map>



#define N 200010

#define int long long

#define INF 0x3f3f3f3f



using namespace std;

int n,a[N];



struct P {

    int val,sum,l,r,siz;

    

    P (int _val=0,int _sum=0,int _l=INF,int _r=0) { val=_val,sum=_sum,l=_l,r=_r,siz=max(_r-_l+1,0ll); }

};

vector<P> stk;

vector<pair<P,int> > pre,suf;



P operator+(P t1,P t2) { return P(t1.val+t2.val+t1.sum*t2.siz,t1.sum+t2.sum,min(t1.l,t2.l),max(t1.r,t2.r)); }

bool operator==(P t1,P t2) { return t1.val==t2.val and t1.l==t2.l and t1.r==t2.r; }

bool operator>(P t1,P t2) {

    if (t1.sum*t2.siz!=t2.sum*t1.siz) return t1.sum*t2.siz>t2.sum*t1.siz;

    return t1.l>t2.l;

}

bool operator>=(P t1,P t2) { return t1>t2 or t1==t2; }

bool operator<(P t1,P t2) { return t2>t1; }

bool operator<=(P t1,P t2) { return t2>=t1; }



const double A=0.65;

int tcnt,rt,flatcnt,flata[N];

struct Tree { P val,sum; int ls,rs,num,siz,sizv,siznd; }t[N];



void upd(int x) {

    t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+t[x].num;

    t[x].sizv=t[t[x].ls].sizv+t[t[x].rs].sizv+1;

    t[x].siznd=t[t[x].ls].siznd+t[t[x].rs].siznd+(t[x].num!=0);

    if (t[x].num>0) t[x].sum=(t[t[x].ls].sum+t[x].val)+t[t[x].rs].sum;

    else t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;

}



bool ifflat(int x) { return t[x].num and (A*t[x].siz<=1.0*max(t[t[x].ls].siz,t[t[x].rs].siz) or A*t[x].sizv>=1.0*t[x].siznd); }



void flatdfs(int x) {

    if (!x) return ;

    flatdfs(t[x].ls);

    if (t[x].num>0) flata[++flatcnt]=x;

    flatdfs(t[x].rs);

}



void flatrebuild(int &x,int l,int r) {

    if (l>r) return void(x=0);

    int mid=(l+r>>1);

    x=flata[mid];

    flatrebuild(t[x].ls,l,mid-1),flatrebuild(t[x].rs,mid+1,r);

    upd(x);

}



void flat(int &x) { flatcnt=0; flatdfs(x); flatrebuild(x,1,flatcnt); }



void ins(int &x,P p) {

    if (!x) {

        t[x=++tcnt]={p,p,0,0,1,1,1,1};

        upd(x); return;

    } else {

        if (t[x].val==p) t[x].num++;

        else if (p<t[x].val) ins(t[x].ls,p);

        else ins(t[x].rs,p);

        upd(x);

        if (ifflat(x)) flat(x);

    }

}



void del(int &x,P p) {

    if (!x or (t[x].val==p and !t[x].num)) return;

    if (t[x].val==p) t[x].num--;

    else if (p<t[x].val) del(t[x].ls,p);

    else del(t[x].rs,p);

    upd(x);

    if (ifflat(x)) flat(x);

}



void dfs(int x) {

    if (!x) return;

    dfs(t[x].ls);

    printf("%lld: %lld %lld %lld\n    %lld %lld %lld %lld\n",x,t[x].ls,t[x].rs,t[x].num,t[x].val.val,t[x].val.sum,t[x].val.l,t[x].val.r);

    printf("    %lld %lld %lld %lld\n",t[x].sum.val,t[x].sum.sum,t[x].sum.l,t[x].sum.r);

    dfs(t[x].rs);

}



signed main() {

    scanf("%lld",&n);

    for (int i=1;i<=n;i++) scanf("%lld",a+i);

    for (int i=1;i<=n;i++) {

        P x=P(a[i],a[i],i,i);

        while (!stk.empty() and stk.back()<=x) {

            P y=stk.back(); stk.pop_back();

            pre.push_back({y,-1}); x=x+y;

        }

        stk.push_back(x); pre.push_back({x,1});



    }

    stk.clear();

    for (int i=n;i;i--) {

        P x=P(a[i],a[i],i,i);

        while (!stk.empty() and stk.back()<=x) {

            P y=stk.back(); stk.pop_back();

            suf.push_back({y,1}); x=x+y;

        }

        stk.push_back(x); suf.push_back({x,-1});

    }

    // for (int i=suf.size()-1;i>=0;i--)

    //     printf("%lld:%lld\n   %lld %lld %lld %lld %lld\n",i,suf[i].second,suf[i].first.val,suf[i].first.sum,suf[i].first.l,suf[i].first.r,suf[i].first.siz);

    // printf("\n");

    for (auto i:stk) ins(rt,i);

    int precnt=-1,sufcnt=suf.size()-1;

    for (int i=1;i<=n;i++) {

        // printf("\n\n!!!!!!%lld\n",i);

        while (sufcnt>=0 and (suf[sufcnt].second!=-1 or suf[sufcnt].first.l!=i+1)) {

            // printf("%lld ",sufcnt);

            if (suf[sufcnt].second==-1) del(rt,suf[sufcnt].first);

            else ins(rt,suf[sufcnt].first);

            --sufcnt;

        }

        // printf("\n");

        printf("%lld ",t[rt].sum.val+a[i]*(n-1));

        // printf("\n");

        while (precnt==-1 or (precnt<pre.size() and pre[precnt].first.r!=i)) {

            ++precnt;

            // printf("%lld ",precnt);

            if (pre[precnt].second==-1) del(rt,pre[precnt].first);

            else ins(rt,pre[precnt].first);

        }

        // printf("\n");

        // dfs(rt);

    }

    printf("\n");

    return 0;

}