#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];
ll ans[N];


typedef struct{
    int l,r;
    ll mn,mx;
}Node;
void __(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    vector<Node> v;
    int l=1;
    for(int i=2;i<=n;i++){
        if(a[i]<a[i-1]){
            v.push_back({l,i-1,a[l],a[i-1]});
            l=i;
        } 
    }
    v.push_back({l,n,a[l],a[n]});
    int t=v.size();
    // cout<<t<<endl;
    priority_queue<ll,vector<ll>,greater<ll>> q;
    // for(int i=1;i<=n;i++){
        for(auto [x,y,u,uu]:v){
            for(int j=x+1;j<=y;j++){
                q.push(a[j]-a[j-1]);
                ans[t]+=(a[j]-a[j-1]);
            }
        }
    // }
    for(int i=t+1;i<=n;i++){
        ans[i]=ans[i-1]-q.top();
        q.pop();
    }
    vector<Node> vv;
    for(int i=t-1;i>=1;i--){
        ll mn=1e18;
        ll mnt;
        for(int j=1;j<v.size();j++){
            ll res=v[j].mx+v[j-1].mx-v[j].mn-v[j-1].mn-(max(v[j].mx,v[j-1].mx)-min(v[j].mn,v[j-1].mn));
            if(res<mn){
                mn=res;
                mnt=j;
            }
        }
        // cout<<mn<<endl;
        ans[i]=ans[i+1]-mn;
        for(int j=0;j<mnt-1;j++) vv.push_back(v[j]);
        vv.push_back({v[mnt-1].l,v[mnt].r,min(v[mnt-1].mn,v[mnt].mn),max(v[mnt-1].mx,v[mnt].mx)});
        for(int j=mnt+1;j<v.size();j++) vv.push_back(v[j]);
        v=vv;
        vv.clear();
    }
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
}


int main(){
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}