#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

int n,a[N],pos[N][],Log[N];

ll ans;

void pre()//预处理ST表

{

    Log[]=-; for(int i=;i<=n;i++) Log[i]=Log[i>>]+;

    for(int i=;i<=n;i++) pos[i][]=i;

    for(int i=;(<<i)<=n;i++)

        for(int j=;j+(<<(i-))<=n;j++)

        {

            if(a[ pos[j][i-] ]>a[ pos[j+(<<(i-))][i-] ]) pos[j][i]=pos[j+(<<(i-))][i-];

            else pos[j][i]=pos[j][i-];

        }

}

inline int query(int l,int r)//区间求最小值

{

    int k=Log[r-l+];

    if(a[ pos[l][k] ]>a[ pos[r-(<<k)+][k] ]) return pos[r-(<<k)+][k];

    return pos[l][k];

}

void f(int l,int r,int tot)//递归处理左右区间,tot是当前已经进行的操作次数

{

    if(l>r) return;

    int t=query(l,r);

    ans+=a[t]-tot;

    f(l,t-,a[t]); f(t+,r,a[t]);

}

int main()

{

    freopen("road.in","r",stdin);

    freopen("road.out","w",stdout);

    n=read();

    for(int i=;i<=n;i++) a[i]=read();

    pre();

    f(,n,);

    cout<<ans<<endl;

    return ;

}