#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("operatii.in");
ofstream cout("operatii.out");
vector<int> pos_by_val[100000];
int n, arr[1000000];
struct min_tree{
    min_tree *a = NULL, *b = NULL;
    int l, r, val;
    int query(int l_, int r_){
        if((l_ == l) && (r_ == r))
            return val;
        else if(l_ >= b->l)
            return b->query(l_, r_);
        else if(r_ < b->l)
            return a->query(l_, r_);
        else return min(a->query(l_, a->r), b->query(b->l, r_));
    }
    int build(int l_, int r_, min_tree *&pre){
        l = l_;
        r = r_;
        if(l == r)
            return val = arr[l_];
        a = pre++;
        b = pre++;
        return val = min(a->build(l_, (l_ + r_)/2, pre), b->build((l_ + r_)/2 + 1, r_, pre));
    }
};
min_tree root, *pre = new min_tree[2100000];
unsigned long long int result = 0;
void process(int l, int r, int outer_min){
    int minval = root.query(l, r);
    result += (minval - outer_min);
    for(int x = l;x<=r;x++){
        if(arr[x] != minval){
            auto nextminiter = upper_bound(pos_by_val[minval].begin(), pos_by_val[minval].end(), x);
            int interval;
            if((nextminiter == pos_by_val[minval].end()) || (*nextminiter > r)){
                interval = r;
            }else interval = *nextminiter - 1;
            process(x, interval, minval);
            x = interval + 1;
        }
    }
}
int main(){
    cin>>n;
    for(int x = 0;x<n;x++){
        cin>>arr[x];
        pos_by_val[arr[x]].push_back(x);
    }
    root.build(0, n - 1, pre);
    process(0, n - 1, 0);
    cout<<result<<'\n';
    return 0;
}