//#include <bits/c++config.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long //不开long long见祖宗！！！！！
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
#define endl '\n'//血的教训！！！！！
//#pragma GCC optimize(3)
using namespace std;
using std::bitset;
using namespace __gnu_pbds;
int read() {
	int x=0;
	bool fu=0;
	char ch=0;
	while(ch>'9'||ch<'0') {
		ch=getchar();
		if(ch=='-')fu=1;
	}
	while(ch<='9'&&ch>='0') x=(x*10+ch-48),ch=getchar();
	return fu?-x:x;
}
ll a[1000002],sq,n,pl[10002],pos;
ll ans;
int gp(int num){
	return (num-1)/sq+1;
}
int getmin(int l,int r){
	ri i;
    ll ans=LLONG_MAX;
	if(r-l<=4*sq){
		F(j,l,r){
			if(a[j]<ans){
				pos=j;
			}
			ans=min(ans,a[j]);
		}return pos;
	}
	for(i=l;i%sq!=1;i++){
		if(a[i]<ans){
			pos=i;
		}
		ans=min(ans,a[i]);
	}for(;gp(i)!=gp(r);i+=sq){
		if(pl[gp(i)]<ans){
			pos=i;
		}
		ans=min(ans,pl[gp(i)]);
	}for(;i<=r;i++){
		if(a[i]<ans){
			pos=i;
		}
		ans=min(ans,a[i]);
	}return getmin(pos,min(pos+sq,(ll)r));
}
void go(int l,int r,ll now){
	if(l>r)return;
	int m=getmin(l,r);
	ans+=a[m]-now;
	go(l,m-1,a[m]);
	go(m+1,r,a[m]);
}
int main(){
    cin>>n;
    sq=sqrt(n);
    F(i,1,n){
    	a[i]=read();
	}
	F(i,1,n){
		pl[gp(i)]=min(pl[gp(i)],a[i]);
	}
	go(1,n,0);
	cout<<ans;
    return 0;
}

第九点WA