#include <bits/stdc++.h>
#define maxN 1000002
#define maxO 3002
#define maxV 100002
#define ll long long
using namespace std;
int n, v[maxN], sol, a[maxN];
ll ans;
vector < int > V[maxV];
void read()
{
    int i;
    freopen("operatii.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);
}
void brut()
{
    int i, j, p = 1;
    for (i = 1; i < maxO; ++ i)
    {
        for (j = p; j <= n; ++ j)
            if (v[j] != 0)
        {
            int minv = v[j];
            p = j;
            while (v[j + 1] != 0 && j <= n)
            {
                ++ j;
                if (v[j] < minv)
                    minv = v[j];
            }
            sol += minv;
            for (;j >= p; -- j)
                v[j] -= minv;
            break;
        }
    }
}
ll optim(int x, int y, int val, int prv)
{
    int i, left = x;
    ll ans = 0LL;
    if (x > y)
        return 0LL;

    if (!V[val].size() || V[val].back() > y)
    return optim(x, y, val + 1, prv);

    if (x == y)
        {
            V[val].pop_back();
            return val - prv;
        }
    int Prv = prv;
    ans += 1LL * (val - Prv);
    while (!V[val].empty())
    {
        int right = V[val].back();
        if (right > y)
            break;
        V[val].pop_back();
        ans += optim(left, right - 1, val + 1, val);
        left = right + 1;
    }
    ans += optim(left, y, val + 1, val);
    return ans;
}
void solve()
{
    int i;
    if (n <= 1)
    brut();
    else
    {
        int m = 0;
        for (i = 1; i <= n; ++ i)
            if (v[i] != v[i - 1] || i == 1)
               a[++ m] = v[i];
        n = m;
        memcpy(v, a, sizeof(a));
        for (i = n; i >= 1; -- i)
            V[v[i]].push_back(i);
        ans = optim(1, n, 0, 0);
    }
}
void write()
{
    freopen("operatii.out", "w", stdout);
    printf("%lld\n", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}