A duplicate minimum must sit on the min-stack, or one pop forgets the other

A min-stack is a pair of stacks $(S,M)$. Stacks are written as sequences with the rightmost entry on top. Both start empty. The operations are \begin{align*} \mathrm{PUSH}(x)&: \begin{cases} \text{push $x$ on $M$ if $M$ is empty or $x\le\mathrm{top}(M)$},\\ \text{then push $x$ on $S$}, \end{cases}\\ \mathrm{POP}()&: \begin{cases} \text{if $\mathrm{top}(S)=\mathrm{top}(M)$, pop $M$},\\ \text{then pop $S$}, \end{cases}\\ \mathrm{MIN}()&:\text{return }\mathrm{top}(M). \end{align*} $\mathrm{POP}$ and $\mathrm{MIN}$ are defined only when $S$ is nonempty. 1. Prove that after every legal operation $M$ is empty if and only if $S$ is empty, and that if $S$ is nonempty then $\mathrm{top}(M)=\min S$. In particular, identify $M$ as the subsequence of bottom-to-top entries of $S$ that are weakly left-to-right minima. 2. Execute $\mathrm{PUSH}(5)$, $\mathrm{PUSH}(2)$, $\mathrm{PUSH}(2)$, $\mathrm{PUSH}(4)$. Record $S$, $M$, and $\mathrm{MIN}$ after each push. Then execute $\mathrm{POP}$ three times. Prove that after the first $2$ is popped one still has $\mathrm{MIN}=2$, and that after the second $2$ is popped one has $\mathrm{MIN}=5$. 3. Repeat the same seven operations with the comparison in $\mathrm{PUSH}$ changed from $x\le\mathrm{top}(M)$ to $x<\mathrm{top}(M)$. Show exactly where the invariant $\mathrm{top}(M)=\min S$ first fails, and compute the false $\mathrm{MIN}$ after the first $2$-pop. 4. Audit a one-field implementation that stores only a running minimum $m$ and, on every pop, either leaves $m$ unchanged or has no recorded predecessor with which to restore $5$. Explain why the companion stack is not a search tree and not a heap. Do not replace the structure by a balanced tree or by a dynamic table, and do not treat duplicate keys as a single occupancy.

The second $2$ satisfies $2\le 2$, so it must be pushed onto $M$. The later $4$ does not.