#include <iostream>

using namespace std;

const int N = 1e5 + 7;

int stk[N], tt, a[N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i ++) cin >> a[i];

    // 维护一个单调递减的栈
    int res = 0;
    for (int i = 0; i < n; i ++) {
        while (tt > 0 && a[stk[tt - 1]] <= a[i]) {
            if (tt >= 2) { // 如果栈中至少有两个元素
                res += (i - stk[tt - 2] - 1) * (min(a[i], a[stk[tt - 2]]) - a[stk[tt - 1]]);
            }
            tt --;
        }
        stk[tt ++] = i;

    }
    cout << res << endl;

    return 0;
}