How to detect stack order?
I couldn't understand your approach exactly (Seems it's correct), but there is a simple rule for impossible orders: The order is impossible $iff$ there is $a_i,a_j,a_k$ such that $a_i &gt; a_k &gt; a_j$ and $i&lt;j&lt;k$. To such a $a_i,a_j,a_k$ we say bad triple.

Why? First you should prove that if there is bad triple then the sequence is impossible, but this is simple and I'll leave it as exercise (middle number couldn't pop sooner than bigger except smaller poped before all of them).

Second you should prove all impossible orders have at least one bad triple, Assume you have a sequence without any bad triple, you could find the order of push and pop so it's not impossible sequence. For reconstructing the push and pop orders just use naive approach (operation is pop while you iterating over consecutive numbers), but for formal proof (for simplicity) you could use induction, assume for all sequences of length $m$ if there isn't bad triple they aren't impossible. For sequence of length $n$, you can set operations as pop (start from end of sequence), while encountering with increasing consecutive numbers, now you have a sequence of length $m$, with $m &lt; n$, without bad triple, so you can reconstruct push and pop for this sequence, so original one wasn't impossible. start of induction is sequence of length 3.