//手搓的分类讨论暴力算法，能过
// #include<bits/stdc++.h>
// using namespace std;

// int a[30010];
// int n;
// vector<pair<int, int>> mh(1, {0, 0});//前下标后值
// long long water =0;

// int main(){
//     cin>>n;
//     for(int i = 0; i < n; i++){
//         cin>>a[i];
//         if(a[i] > mh[0].second){
//             mh.clear();
//             mh.push_back({i, a[i]});
//         }
//         else if(a[i] == mh[0].second){
//             mh.push_back({i, a[i]});
//         }
//     }

//     //最左边的最长柱左边积水
//     int i = 0, j = 0;
//     while(++i){
//         if(a[i] > a[j]){
//             int width = i-j-1;
//             int height = a[j];
//             water += width*height;
//             j++;
//             while(j < i){
//                 water -= a[j];
//                 j++;
//             }
//         }
//         if(a[i] == mh[0].second) break;
//     }
//     //最右边的最长柱右边积水
//     i = n-1;
//     j = n-1;
//     while(--i){
//         if(a[i] > a[j]){
//             int width = j - i -1;
//             int height = a[j];
//             water += width * height;
//             j--;
//             while(j > i){
//                 water -= a[j];
//                 j--;
//             }
//         }
//         if(a[i] == mh.back().second) break;
//     }
//     //复数最长柱之间的积水
//     if(mh.size() > 1){
//         for(int i = mh.front().first + 1; i < mh.back().first; i++){
//             water += (mh[0].second - a[i]);
//         }
//     }
//     cout<<water<<endl;
// }

//单调栈正解
#include<bits/stdc++.h>
using namespace std;

int n;
stack<int> s;
long long res=0;

int main(){
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin>>v[i];
        while(s.size() && v[i] > v[s.top()]){
            int right = i;
            int bottom = s.top();
            s.pop();
            if(s.size()){
                int left = s.top();
                res += (min(v[right], v[left])-v[bottom]) * (right - left -1);
            }
        }
        s.push(i);
    }
    cout<<res;
}