#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e12+2;
const int NMAX = 1e5+2;
int n,v[NMAX];

ifstream fin("biscuiti.in");
ofstream fout("biscuiti.out");

struct Node{
    int lazy = 0, val = 0, mini = INF, poz = 0;
    Node operator + (const Node &aux) const {
        Node ans;
        ans.mini = (mini <= aux.mini ? mini : aux.mini);
        ans.poz = (mini <= aux.mini ? poz : aux.poz);
        return ans;
    }
    void add(int x){
        mini += x;
    }
} aint[4*NMAX];

void propag(int nod){
    if(aint[nod].lazy){
        aint[nod].lazy = 0;

        aint[2*nod].lazy = aint[2*nod+1].lazy = 1;
        aint[2*nod].val += aint[nod].val;
        aint[2*nod+1].val += aint[nod].val;

        aint[2*nod].add(aint[nod].val);
        aint[2*nod+1].add(aint[nod].val);

        aint[nod].val = 0;
    }
}

void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].mini = v[st];
        aint[nod].poz = st;
    }else{
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

int query(int nod, int st, int dr, int pos){
    if(st == dr){
        return aint[nod].mini;
    }else{
        propag(nod);
        int mid = (st+dr)/2;
        if(pos <= mid){
            return query(2*nod, st, mid, pos);
        }
        return query(2*nod+1, mid+1, dr, pos);
    }
}

void update(int nod, int st, int dr, int l, int r, int val){
    if(l <= st && dr <= r){
        aint[nod].lazy = 1;
        aint[nod].val += val;
        aint[nod].mini += val;
    }else{
        propag(nod);
        int mid = (st+dr)/2;
        if(l <= mid){
            update(2*nod, st, mid, l, r, val);
        }
        if(r >= mid+1){
            update(2*nod+1, mid+1, dr, l, r, val);
        }
        aint[nod] = aint[2*nod] + aint[2*nod+1];
    }
}

signed main()
{
    fin >> n;
    int sum = 0;
    for(int i = 1; i <= n; i++){
        fin >> v[i];
        sum += v[i];
    }
    build(1, 1, n);
    int ans = 0;
    for(int t = 1; t <= n; t++){
        int poz = aint[1].poz;
        ans += aint[1].mini;
        update(1, 1, n, poz, poz, INF);
        update(1, 1, n, 1, poz, t);
    }
    fout << ans-sum;
    return 0;
}