Red-Blue Sort

You are given a permutation$^\dagger$ $P$ of the integers $1$ to $N$. You can perform the following three-step operation on it as many times as you like (possibly, zero): - First, choose any [subset](https://en.wikipedia.org/wiki/Subset) $S$ of indices of $P$, whose size is between $1$ and $N-1$. (That is, $S$ should not be the empty set or the entirety of $\{1, 2, \ldots, N\}$.) Note that $S$