Rain water trapping

// https://www.youtube.com/watch?v=FbGG2qpNp4U&list=PL_z_8CaSLPWdeOezg68SKkeLN4-T_jNHd&index=9&ab_channel=AdityaVerma

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

int main(){

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n;
    cin>>n;

    int *arr = new int[n];
    for(int i=0; i<n; i++) cin>>arr[i];

    stack<int> s;
    int ttl=0,sumTill=0;
    set<int> inds;

    s.push(0);

    for(int i=1; i<n; i++){
        if(arr[i]<=arr[s.top()]){
            sumTill+=arr[i];
        }else{
            ttl+=(i-s.top()-1)*arr[s.top()] - sumTill;
            sumTill=0;
            inds.insert(i);
            s.pop();
            s.push(i);
        }

    }

    sumTill=0;

    while(!s.empty()) s.pop();
    s.push(n-1);
    for(int i=n-2; i>=0; i--){
        if(arr[i]<=arr[s.top()]){
            sumTill+=arr[i];
        }else{
            ttl+=(s.top()-i-1)*arr[s.top()] - sumTill;
            sumTill=0;

            if(inds.find(i) != inds.end()) break;
            s.pop();
            s.push(i);
        }
    }

    cout<<ttl<<endl;

    delete[] arr;

    return 0;
}