Counting Number of Rectangles in a 2d histogram with area >=K

Question

The problem is in a 2d histogram with N columns, counting number of rectangles with area ≥ K. The columns have width 1 and I know the number of unit squares on the i^th column.

I've come up with the following O(N²) algorithm: let h_i be the height of the i ^th column. Then I can do the following: when I fix i,j as our bottom side of rectangle, I find the highest possible height of the rectangle h and add max(0, h - ceil(K/(j-i+1)) + 1) to the answer.

I heard there is an O(N log N) algorithm, and I tried to derive it by using the fact

∑^N_i=1^N⁄_i  ~ N log N

However, that's all I have and I can't make further progress. Can you give a hint on the algorithm?