Validating sequence of intermixed push and pop operations on Stack

I was reading this interesting problem on Stackoverflow:

http://stackoverflow.com/questions/10445364/intermixed-sequence-of-push-and-pop-operations-why-is-this-sequence-not-possilbe

The problem is not as complex as it seems at first glance. It clearly stipulates a condition for legitimate push: you may only push values in ascending order. 

Here, the key is to look at a sequence, and when you see a number k in it, understand that all numbers 0,1,2,3,..,k (all m < k) get pushed first. That is, you may not push any r > k before k has itself been pushed on to the stack.

With the retention of that simple idea, you can land at the solution pretty easily.