Ginmans Stack are a kind of special data structure in which if there are odd number of elements then the middle most element is popped out and printed on the screen. In case of even number of elements the recently popped out element is again pushed back either on the top or bottom of the stack randomly.
Assume initially Ginmans Stack has elements $p_1, p_2, \dots p_{N-1}$ where $N$ is even, $p_1$ and $p_{N-1}$ denotes the bottom and top of the stack respectively.
Consider the following printing sequences:
('*' here denotes repetitions zero or more number of times)
Which of the following printing sequence is not possible?
- $\{p_{N/2}p_{N/2-1}p_{N/2-2} \dots p_1\}^*$
- $\{p_{N/2}p_{N/2+1}p_{N/2-1} \dots p_1\}^*$
- $\{p_{N/2}p_{N/2-1}p_{N/2-2} \dots p_{N/2}\}^*$
- $\{p_{N/2}p_{N/2+1}p_{N/2-1} \dots p_{N/2}\}^*$
- i, ii
- ii, iii
- iii, iv
- ii, iv