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


using namespace std;

const int mxn = 100 * 1000 + 10;
const ll mxx = 1e11;

ll arb[ mxn * 4 ];
ll arb_sum[ mxn * 4 ];

int n;
ll s_initial, s_final;

int gard[ mxn ];

int poz_min;

void construire(int nod, int st, int sf){
    if(st == sf){
        arb[ nod ] = gard[ st ];
    }
    else{
        int mid = (st + sf) / 2;
        construire(2 * nod, st, mid);
        construire(2 * nod + 1, mid + 1, sf);
        arb[ nod ] = min(arb[ 2 * nod ], arb[ 2 * nod + 1 ] );
    }
}

void afisare(int nod, int st, int sf, ll v[]){
    cout<< st << ' ' << sf << ' ' << v[ nod ] << '\n';
    if(st < sf){
        int mid = (st + sf) / 2;
        afisare(2 * nod, st, mid, v);
        afisare(2 * nod  + 1, mid + 1, sf, v);
    }
}

void query(int nod, int st, int sf){
    if(st == sf){
        poz_min = st;
        arb[ nod ] = mxx;
    }
    else{
        int mid = (st + sf) / 2;
        int p1 = 2 * nod;
        int p2 = 2 * nod + 1;
        ll t = arb_sum[ nod ];
        arb_sum[ nod ] = 0;

        arb[ p1 ] += t;
        arb_sum[ p1 ] += t;
        arb[ p2 ] += t;
        arb_sum[ p2 ] += t;
        if(arb[ p1 ] <= arb[ p2 ])
            query(p1, st, mid);
        else
            query(p2, mid + 1, sf);
        arb[ nod ] = min(arb[ p1 ], arb[ p2 ]);
    }
}

void update(int nod, int st, int sf, ll adun){
    if(st >= poz_min)
        return;
    int mid = (st + sf) / 2;
    int p1 = 2 * nod;
    int p2 = 2 * nod + 1;
    ll t = arb_sum[ nod ];
    arb_sum[ nod ] = 0;

    arb[ p1 ] += t;
    arb_sum[ p1 ] += t;
    arb[ p2 ] += t;
    arb_sum[ p2 ] += t;
    if(mid < poz_min){
        arb[ p1 ] += adun;
        arb_sum[ p1 ] += adun;
        update(p2, mid + 1, sf, adun);
    }
    else{
        update(p1, st, mid, adun);
    }
    arb[ nod ] = min(arb[ p1 ], arb[ p2 ]);
}

int main()
{
    ifstream cin("biscuiti.in");
    ofstream cout("biscuiti.out");
    cin>> n;
    for(int i = 1, x; i <= n; i++){
        cin>> x;
        gard[ i ] = x;
        s_initial += x;
    }
    construire(1, 1, n);

    for(int i = 1; i <= n; i++){
        s_final += arb[ 1 ];
        query(1, 1, n);
        update(1, 1, n, i);
    }
    cout<< s_final - s_initial;
    return 0;
}