#include <cassert>
#include <stack>
#include <vector>
using namespace std;

int trap_rain_water(const vector<int> &h) {
  int sum = 0;

  stack<int> last_seen_level_at;
  int last_i = 0;
  for (int col = 0; col < h.size(); ++col) {
    int i = h[col];

    if (i > last_i) {
      // flush prev levels below
      for (auto k = i; k > last_i; --k) {
        if (!last_seen_level_at.empty()) {
          sum += (col - last_seen_level_at.top());
          last_seen_level_at.pop();
        }
      }
    }

    if (i < last_i) {
      // track start col of levels
      for (auto k = last_i; k > i; --k) {
        last_seen_level_at.push(col);
      }
    }

    last_i = i;
  }
  return sum;
}

int main() {
  // www.youtube.com/watch?v=HmBbcDiJapY&t=333s
  vector<int> h = {1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
  int result = 1 + 1 + 2 + 1 + 1;

  assert(trap_rain_water(h) == result);
  return 0;
}