• 对于每个柱子，分别找到左右两边最高的柱子 $l_i$ 和 $r_i$
• 而 $l_i$ 和 $r_i$ 中较低的那个高度，就是当前柱子接雨水的高度

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

i64 solve(vector<int>& a) {
    int n = a.size();

    // L(i): [a(0), a(1), ... a(i)] 最大的数
    vector<int> L(n, a[0]);
    for (int i = 1; i < n; i++) L[i] = max(L[i - 1], a[i]);

    // R(i): [a(i), a(i + 1), ... a(n - 1)] 最大的数
    vector<int> R(n, a[n - 1]);
    for (int i = n - 2; i >= 0; i--) R[i] = max(R[i + 1], a[i]);

    i64 ans = 0;
    for (int i = 1; i < n - 1; i++) {
        // 左右两边的最大值, 取较小的那个
        ans += min(L[i], R[i]) - a[i];
    }
    return ans;
}

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << solve(a) << '\n';

    return 0;
}