= Solution
<Monotonicity> gives two excluded rectangles:
$$
\boxed{\begin{aligned}
0\leq r\leq i,\quad 0\leq c<j&\implies f[r,c]<x,\\
i\leq r<M,\quad j\leq c<N&\implies f[r,c]>x.
\end{aligned}}
$$
Indeed the first entries are at most $f[i,j-1]$, and the second are at least $f[i,j]$. In particular, the entire splitting row $i$ contains no answer. The only remaining candidates are the upper-right rectangle $r<i,c\geq j$ and the lower-left rectangle $r>i,c<j$. These are the exclusions guaranteed by the given adjacent inequalities; further comparisons may exclude more.
Back to article page
