#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 9;
int a[N];
int l[N];
int r[N];
int ans = 0;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int mid = a[1];
for(int i=2;i<=n;i++){
if(mid<a[i]) mid = a[i];
l[i] = mid;
}
mid = a[n];
for(int i=n-1;i>=1;i--){
if(mid<a[i]) mid = a[i];
r[i] = mid;
}
for(int i=1;i<=n;i++){
if(a[i]<min(l[i],r[i])) ans+=min(l[i],r[i])-a[i];
}
cout<<ans;
}

dp算法

能接雨水的条件是中间比左右两边都低，所以我们遍历两次，第一次，从左到右遍历一遍，以左边的高度为标准，去接雨水。第二次从右到左遍历一遍，以右边高度为标准去接雨水，由于左右高度是以低的高度作为标准，所以遍历比较每个位置的两次所取的雨水值，取低的加起来即为答案

#include<bits/stdc++.h>
using namespace std;
# define N 30005
int n,a[N],b[N],dp1[N],dp2[N],sum=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	for(int i=2;i<n;i++) #从左到右
	{
		if(a[i]>=a[i-1])
		{
			dp1[i]=0;
		}
		else if(a[i]<a[i-1])
		{
			dp1[i]=a[i-1]-a[i];
			a[i]=a[i-1];
		}
	}
	for(int i=n-1;i>=2;i--) #从右到左
	{
		if(b[i]>=b[i+1])
		{
			dp2[i]=0;
		}
		else if(b[i]<b[i+1])
		{
			dp2[i]=b[i+1]-b[i];
			b[i]=b[i+1];
		}
	}
	for(int i=2;i<n;i++)   #取最小
	{
		dp1[i]=min(dp1[i],dp2[i]);
	}
	for(int i=1;i<=n;i++)
	{
		sum+=dp1[i];
	}
	cout<<sum;
	return 0;
}

//手搓的分类讨论暴力算法，能过
// #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;
}