#include <bits/stdc++.h>>

using namespace std;

typedef long long ll;
#define int ll

const int N=2e5+10;

int a[N];

signed main()
{
    int n;
    cin>>n;
    map< int, set< pair<int,int> > , greater<int> > m;
    for(int i=1;i<=n;i++)
        cin>>a[i],m[a[i]].insert(make_pair(i,i));
    m[0];
    int ans=0;
    while(m.size()>1)
    {
        if(m.begin()->second.empty())
        {
            m.erase(m.begin());
            continue;
        }
        int x=m.begin()->first;
        #define v (m.begin()->second)
        int l=v.begin()->first,r=v.begin()->second;
        v.erase(v.begin());
        while(!v.empty()&&v.begin()->first==r+1)
        {
            r=v.begin()->second;
            v.erase(v.begin());
        }
        int t=max(a[l-1],a[r+1]);
        m[t].insert(make_pair(l,r));
        ans+=x-t;
        #undef v
    }
    cout<<ans;
}
