1. 维护一个单调减小的栈，若当前柱子高于栈顶的柱子，退栈直到符合单调性；否则加入栈顶。
2. 每次退栈时，累加雨水的体积（每次算一层）。
3. 最后栈是一个单调栈，结束程序即可

# include <iostream>
# include <stack>

using namespace std;

const int N = 100010;
int a[N];

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

    stack<int> st;
    for (int i=0; i<n; i++){
        while(!st.empty() && a[st.top()] < a[i]){
            int t = st.top();
            st.pop();
            if (!st.empty()){
                int l = i - st.top() - 1;
                int h = min(a[i], a[st.top()]) - a[t];
                res += l * h;
            }
        }
        st.push(i);
    }
    cout << res << endl;
    return 0;
}