#include <cstdio>
#include <algorithm>
#include <iostream>
#define pii pair<int,int>
#define mp make_pair
#define ll long long
#define N 222222
using namespace std;

struct tree{
    int l,r,add;
    pii mx,mn;
} t[4*N];

int a[N],n;
ll ans;

void build(int x,int l,int r){
    t[x].l=l;t[x].r=r;t[x].add=0;
    if (l==r){
        t[x].mx.first=a[l];
        t[x].mn.first=a[l];
        t[x].mx.second=l;
        t[x].mn.second=l;
        return;
    }
    build(x+x,l,(l+r)/2);
    build(x+x+1,(l+r)/2+1,r);
    t[x].mx=max(t[x+x].mx,t[x+x+1].mx);
    t[x].mn=min(t[x+x].mn,t[x+x+1].mn);
}

pii get_max(int x,int l,int r,int sum=0){
    if (t[x].l>r || t[x].r<l) return mp(-(1<<30),-1);
    if (t[x].l>=l && t[x].r<=r) return mp(t[x].mx.first+t[x].add+sum,t[x].mx.second);
    return max(get_max(x+x,l,r,sum+t[x].add),get_max(x+x+1,l,r,sum+t[x].add));
}

pii get_min(int x,int l,int r,int sum=0){
    if (t[x].l>r || t[x].r<l) return mp(1<<30,-1);
    if (t[x].l>=l && t[x].r<=r) return mp(t[x].mn.first+t[x].add+sum,t[x].mn.second);
    return min(get_min(x+x,l,r,sum+t[x].add),get_min(x+x+1,l,r,sum+t[x].add));
}

void modify(int x,int l,int r,int add){
    if (t[x].r<l || t[x].l>r) return;
    if (l<=t[x].l && r>=t[x].r){
        t[x].add+=add;
        return;
    }
    modify(x+x,l,r,add);
    modify(x+x+1,l,r,add);
    t[x].mx=max(mp(t[x+x].mx.first+t[x+x].add,t[x+x].mx.second),mp(t[x+x+1].mx.first+t[x+x+1].add,t[x+x+1].mx.second));
    t[x].mn=min(mp(t[x+x].mn.first+t[x+x].add,t[x+x].mn.second),mp(t[x+x+1].mn.first+t[x+x+1].add,t[x+x+1].mn.second));
}

void init(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
}

void sol(int L,int R,int up){
    if (R<L) return;
    pii mn=get_min(1,L,R),mx=get_max(1,L,R);
    if (mn.first==mx.first){
        ans+=up-mn.first;
        modify(1,L,R,up-mn.first);
        return;
    }
    int f=mx.first,r=R;
    while (1){
        if (L>r) break;
        pii a=get_max(1,L,r);
        if (a.first!=f){
            sol(L,r,f);
            break;
        }
        sol(a.second+1,r,f);
        r=a.second-1;
    }
    ans+=up-f;
    modify(1,L,R,up-f);
}

int main(){
    init();
    int f=*max_element(a+1,a+n+1);
    int l=1;
    for (int i=1;i<=n;i++) if (a[i]==f){
        sol(l,i-1,f);
        l=i+1;
    }
    sol(l,n,f);
    printf("%I64d\n",ans);
    return 0;
}