#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 or t2==t1; }



const double A=0.75;

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

struct Tree { P val; int ls,rs,num,siz,sizv,siznd; int Val,Sum,Siz; }t[N<<3];



void upd(int x) {

    t[x].Siz=t[t[x].ls].Siz+t[t[x].rs].Siz+(t[x].num>0?t[x].val.siz:0);

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

    if (t[x].num) t[x].Val=t[t[x].ls].Val+t[x].val.val+t[t[x].rs].Val+t[x].val.sum*t[t[x].rs].Siz+t[t[x].ls].Sum*(t[x].val.siz+t[t[x].rs].Siz);

    else t[x].Val=t[t[x].ls].Val+t[t[x].rs].Val+t[t[x].ls].Sum*t[t[x].rs].Siz;

    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);

}



bool ifflat(int x) { return (t[x].num>0 and (t[x].siz*A<=(double)std::max(t[t[x].ls].siz,t[t[x].rs].siz) or (t[x].sizv*A>=(double)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,0,0,1,1,1,1,p.val,p.sum,p.siz};

        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) 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);

}



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 (auto i:stk) ins(rt,i);

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

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

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

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

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

            --sufcnt;

        }

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

        if (i!=n) printf(" ");

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

            ++precnt;

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

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

        }

    }

    printf("\n");

    return 0;

}