Monotony

You are given an $r\! \times \! c$ grid. Each cell of this grid is filled with a number between $1$ and $r{\cdot }c$ inclusive, and each cell’s number is distinct.

Define a grid of numbers to be *monotonic* if each row and column is either
increasing or decreasing (this can be different for each row or
column).

Define a *subgrid* of the grid as
follows: First choose some nonempty subset of the rows and
columns. Next, take elements that lie in both the chosen rows
and columns in the same order.

There are $(2^ r{-}1)(2^ c{-}1)$ nonempty subgrids of the given grid. Of these subgrids, count how many are monotonic.

Consider this grid:

$7$ $6$ $4$

$9$ $8$ $3$

There are nine $1{\times }1$ subgrids, nine $1{\times }2$’s, three $1{\times }3$’s, nine $2{\times }1$’s, nine $2{\times }2$’s, three $2{\times }3$’s, three $3{\times }1$’s, three $3{\times }2$’s, and one $3{\times }3$. They are all monotonic, for $9{+}9{+}3{+}9{+}9{+}3{+}3{+}3{+}1=49$ monotonic subgrids.

Each test case will begin with a line with two space-separated integers $r$ and $c$ ($1\! \le \! r,c\! \le \! 20$), which are the dimensions of the grid.

Each of the next $r$ lines will contain $c$ space-separated integers $x$ ($1\! \le \! x\! \le \! r{\cdot }c$, all $x$’s are unique). This is the grid.

Output a single integer, which is the number of monotonic subgrids in the given grid.

Sample Input 1 | Sample Output 1 |
---|---|

3 3 1 2 5 7 6 4 9 8 3 |
49 |

Sample Input 2 | Sample Output 2 |
---|---|

4 3 8 2 5 12 9 6 3 1 10 11 7 4 |
64 |