#include <bits/stdc++.h>

using namespace std;
const int inf=2000000001;
vector<int> llink,rlink;
vector<int> v;
int n;
void erase_el(int pos){
    v[pos]=-1;
    int l,r;
    if(pos==0)
        l=-1;
    else
        l=llink[pos-1];
    if(pos==n-1)
        r=n;
    else
        r=rlink[pos+1];
    rlink[l+1]=r;
    llink[r-1]=l;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int p=-1;
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        if(i==0){
            p=x;
        }
        else if(x!=p){
            v.push_back(p);
            p=x;
        }
    }
    v.push_back(p);
    n=v.size();
    if(n==1){
        cout << v[0];
        return 0;
    }
    multiset<pair<int,int> > q;
    llink.resize(n);
    rlink.resize(n);
    for(int i=0; i<n; i++){
        q.insert(make_pair(v[i],i));
        llink[i]=i;
        rlink[i]=i;
    }
    long long ans=0;
    while(q.size()>1){
        multiset<pair<int,int> >::iterator it=q.end();
        --it;
        pair<int,int> cur=*it;
        q.erase(it);
        int pos=cur.second;
        int l,r;
        if(pos==0)
            l=-1;
        else
            l=llink[pos-1];
        if(pos==n-1)
            r=n;
        else
            r=rlink[pos+1];
        int mx=-inf;
        if(l!=-1)
            mx=max(mx,v[l]);
        if(r!=n)
            mx=max(mx,v[r]);
        ans+=cur.first-mx;
        v[pos]=mx;
        if(l!=-1 && v[l]==mx){
            erase_el(l);
            q.erase(q.find(make_pair(mx,l)));
        }
        if(r!=n && v[r]==mx){
            erase_el(r);
            q.erase(q.find(make_pair(mx,r)));
        }
        q.insert(make_pair(mx,pos));
    }
    if(!q.empty()){
        ans+=q.begin()->first;
    }
    cout << ans;
}
