class Solution {
public:
  int h[100005], sums[100005], fle[100005];
  int trap(vector<int>& height) {
    int n = height.size();
    for(int i = 1; i <= n; ++i) {
      h[i] = height[i - 1];
      sums[i] = sums[i - 1] + h[i];
    }
    fle[1] = 1;
    int best = 0;
    for (int i = 2; i <= n; ++i) {
      int idx = i - 1;
      while (fle[idx] != idx && h[idx] < h[i]) {
        idx = fle[idx];
      }
      if(h[idx] >= h[i]) fle[i] = idx;
      else fle[i] = i;
      best = max(best, (i - idx - 1) * min(h[i], h[idx]) - (sums[i - 1] - sums[idx]));
    }
    return best;
  }
};