#include <fstream>
#include <queue>
#include <algorithm>

#define ll long long

using namespace std;

ifstream cin("operatii.in");
ofstream cout("operatii.out");

const int NMAX = 1e6;
//const int VMAX = 1e5;

struct DSU {
    ll components;
    int parent[NMAX + 1];
    int sz[NMAX + 1];

    void init(int n) {
        components = 0;
        for(int i = 1; i <= n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    int get_root(int node) {
        return parent[node] = (parent[node] == node ? node : get_root(parent[node]));
    }

    void join(int x, int y) {
        x = get_root(x);
        y = get_root(y);
        if(x == y) {
            return;
        }

        if(sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        parent[x] = y;
        components--;
    }
}dsu;

int n;
ll answer;
pair<ll, ll> a[NMAX + 1];
ll b[NMAX + 1];

signed main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].first;
        b[i] = a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1, greater<pair<int, int>>());
    dsu.init(n);
    int i = 1;
    while(i <= n) {
        int j = i;
        while(j <= n && a[j].first == a[i].first) {
            j++;
        }
        dsu.components += j - i;
        for(int k = i; k < j; k++) {
            int pos = a[k].second;
            if(pos - 1 >= 1 && b[pos - 1] >= b[pos]) {
                dsu.join(pos - 1, pos);
            }
            if(pos + 1 <= n && b[pos + 1] >= b[pos]) {
                dsu.join(pos + 1, pos);
            }
        }
        answer += dsu.components * (a[i].first - a[j].first);
        i = j;
    }
    cout << answer << '\n';
    return 0;
}