#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Nmax = 2e5 + 2;

struct pos {
    int val, i;
};
bool operator < (pos a, pos b) {
    return a.val > b.val;
}
pos arr[Nmax];
bool used[Nmax];

int main() {
    int n;
    cin >> n;
    for(int i = 0;i < n;++i) {
        cin >> arr[i].val;
        arr[i].i = i;
        used[i] = false;
    }
    sort(arr, arr+n);

    int k, cur, hV;
    ll ans = 0;
    k = 1;
    cur = arr[0].val;
    used[arr[0].i] = true;
    for(int i = 1;i < n;++i) {
        ans += 1ll*k*(cur-arr[i].val);
        cur = arr[i].val;
        hV = arr[i].i;
        if(hV > 0 && hV < n-1 && used[hV-1] && used[hV+1])
            k--;
        if((hV == 0 || !used[hV-1]) && (hV == n-1 || !used[hV+1]))
            k++;
        used[hV] = true;

    }
    cout << ans + cur << '\n';
    return 0;
}
