Linear time algorithm for slicing stacked boxes

I have a problem which has a rather limited time constraint, and would like to see if I could get a nudge in the right direction.

Here is the problem:

You are presented with a wall with columns of different heights. Each column heights is represented as a non-zero integers.

Input state is defined using an array H of length N, containing heights of each of the N columns on the screen, for example:

Slicing the snapshot at a given height leaves a number of solid pieces above that height. E.g. slicing at level 2 would cut 3 solid pieces:

Slicing at level 1 would also cut 3 solid pieces:

Similarly, slicing at level 0 would return a single (one) solid piece, while slicing at level 3 wouldn't cut any pieces.

Requirement: Given an array of slice heights S of length M, containing all levels at which a "slice" should be performed, return an array of length M containing numbers of cut pieces for each respective cut.

For example, given the input H = {2, 1, 3, 2, 3, 1, 1, 2} and S = { 0, 1, 2, 3 }, the program should return quantities {1, 3, 3, 0}, according to the examples above.

Both N and M are in the range of around 20,000, but heights in each array can reach up to 1,000,000.

Both time and space worst-case complexity for the solution cannot exceed O(N + M + max(M) + max(N)).

The last constraint is what puzzles me: it basically means that I cannot have any nested for-loops, and I cannot seem to escape this.

Obviously, there is some clever preprocessing which needs to be done to yield final results in O(1) per slice, but I haven't been able to come up with it.

I went on to create an array of cut numbers for each slice level, and then update all of them as I iterate through H, but this turns out to be O(N*M), since I need to update all lower height levels.

Is there a data structure which would be appropriate for this task?