#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void chmin(ll& a, ll b) { if(a > b) a = b; }
void chmax(ll& a, ll b) { if(a < b) a = b; }
#define all(A) begin(A), end(A)


/*
    saishuutekina yama wo u[i] to suru
    h[i] no hikui junnni fuyasu
    h[i] tte unique? tabun
    for x = min(h), ...:
        h.strip(x)
        h[i] == x de aru connected component to h[i] > x de aru CC ni wakete, saishouti wo kannri
        leftmost, rightmost ha 1 kai erabareru
        h[i] > x de aru CC no min{h[i]} no retsu wo U[1], ..., U[k] to suru
        D := #{i | h[i] == x}
        D == 1 ==> cost = U[1] + U[2]
        else ==> cost = U[1] + U[k] + min(U) + (2 * D - 3) * (x + 1)
    dekita
*/
struct ST {
    ll lg = 0;
    vector<vector<ll>> table;
    ST(vector<ll> a) {
        while((2 << lg) <= a.size()) lg++;
        table.resize(lg + 1, a);
        for(ll l = 0; l < lg; l++) for(ll i = 0; i + (2 << l) <= a.size(); i++) {
            table[l + 1][i] = min(table[l][i], table[l][i + (1 << l)]);
        }
    }
    ll get(ll L, ll R) {
        if(L == R) return LLONG_MAX;
        const ll l = __lg(R - L);
        return min(table[l][L], table[l][R - (1 << l)]);
    }
};
int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    ll N;
    cin >> N;
    vector<ll> H(N);
    for(ll& h : H) cin >> h;
    auto X = H;
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    vector idx(N, 0LL);
    for(ll i = 0; i < N; i++) idx[i] = i;
    sort(all(idx), [&](ll i, ll j) { return H[i] > H[j]; });
    ST st(H);
    ll D = 0, L = 0, R = N, ans = 0;
    for(ll x = 0; x + 1 < X.size(); x++) {
        const ll h = X[x], h2 = X[x + 1];
        while(idx.size() && H[idx.back()] == h) {
            idx.pop_back();
            D++;
        }
        while(L < R && H[L] <= h) {
            L++; D--;
        }
        while(L < R && H[R - 1] <= h) {
            R--; D--;
        }
        const ll U1 = [&]{
            ll ok = L + 1, ng = R + 1;
            while(ng - ok > 1) {
                const ll mid = (ok + ng) / 2;
                (st.get(L, mid) > h ? ok : ng) = mid;
            }
            return st.get(L, ok);
        }();
        const ll U2 = [&]{
            ll ok = R - 1, ng = L - 1;
            while(ok - ng > 1) {
                const ll mid = (ok + ng) / 2;
                (st.get(mid, R) > h ? ok : ng) = mid;
            }
            return st.get(ok, R);
        }();
        const ll U3 = X[x + 1];

        if(D == 0) continue;
        ans += D * (h2 - h) * (h + h2 - 1) / 2;
        if(D == 1) ans += (h2 - h) * (U1 + U2);
        else {
            ans += (h2 - h) * (h + h2 + 1) / 2 * (D * 2 - 3);
            ans += (h2 - h) * (U1 + U2 + U3);
        }
    }
    cout << ans << endl;
}