Linear Solution

Create a histogram where the height at ~i~ is ~h_i - \max f_i~. If there is no forbidden floor at ~i~, the histogram height at ~i~ will be set to "infinity". Now the problem is reduced to finding the maximum rectangle area in the histogram, but the area cannot be greater than or equal to "infinity". Set an "infinity" value larger than the largest area possible value, ~N \times \max h_i~. ~N^2 \times \max h_i~ (every building except for one is infinity) will not overflow a ~64~-bit integer.

Note that there are many other solutions to this problem and ~\mathcal O(N \log N)~ solutions also pass.

Intended Complexity: ~\mathcal O(N)~