//本题数学思路：用单调栈找每个柱子左边第一个比它高的位置，累加两柱之间的储雨量
//两柱体间的雨水容量 = 左边柱体与水面高度差 * 两柱体间的距离(具体推导可见第一篇题解)

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N];  //用栈存储单调不增的元素下标
int a[N];
int tt;

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++){
        int water = 0; //记录水面高度，每次计算都需重置水面高度
        while(tt && a[stk[tt]] <= a[i]){   //单调栈的运用
            res += (a[stk[tt]] - water) * (i - stk[tt] - 1);   //容量计算
            water = a[stk[tt]];
            tt--;
        }
        if(tt){   //将新柱的高度压入单调栈后，若其不为栈底元素，则说明左边存在比它更高的柱子，故此时已"a[i]"作为计算用的高度差
            res += (a[i] - water) * (i - stk[tt] - 1);    //第一篇题解图示④的情况
        }
        stk[++tt] = i;
    }

    cout << res << endl;

    return 0;
}