#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;
ll ans;
vector < int > V[maxV];
class InputReader
{
public:
    InputReader() {}
    InputReader(const char *file_name)
    {
        input_file = fopen(file_name, "r");
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }
    inline InputReader &operator >>(int &n)
    {
        while(buffer[cursor] < '0' || buffer[cursor] > '9')
        {
            advance();
        }
        n = 0;
        while('0' <= buffer[cursor] && buffer[cursor] <= '9')
        {
            n = n * 10 + buffer[cursor] - '0';
            advance();
        }
        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE = 1 << 17;
    int cursor;
    char buffer[SIZE];
    inline void advance()
    {
        ++ cursor;
        if(cursor == SIZE)
        {
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
    }
};
void read()
{
    int i, x, m = 0;
    InputReader cin("operatii.in");
    cin >> n;
    for (i = 1; i <= n; ++ i)
        {
            cin >> x;
            if (x != v[m] || i == 1)
                v[++ m] = x;
        }
    n = m;
}
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
    {
        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;
}