Counting Rectangular Decreasing Paths

JOI played on the beach, where he built a sandcastle within a rectangular region of the beach that has $H$ rows and $W$ columns. The height of the cell in the $i$-th row and the $j$-th column is given by $A_{i,j}$, and all the $A_{i,j}$ are distinct.

JOI performs the following actions on his sandcastle:

1. He chooses an arbitrary cell to start from.
2. Then, he repeatedly moves from the current cell to one of its four adjacent cells (up, down, left, or right), provided that the next cell has a strictly lower height than the current one. He may perform this move zero or more times.

After his moves, the set of cells he visited is observed from above and forms a rectangle. In other words, there exist integers $r_1$, $r_2$, $c_1$, and $c_2$ such that the visited cells are exactly those in rows $r_1$ to $r_2$ and columns $c_1$ to $c_2$.

For any rectangular region (subrectangle) of the grid, the only candidate ordering that can satisfy the rule of moving only to a cell with lower height is the unique order obtained by sorting all cells in the rectangle in descending order of their heights. The path is considered valid if, when the cells are arranged in this descending order, every two consecutive cells are adjacent (i.e. their Manhattan distance is 1).

Your task is to count the number of subrectangles for which the sorted (descending) order of the cells forms a valid path.

inputFormat

The first line contains two integers $H$ and $W$.

Each of the following $H$ lines contains $W$ space-separated integers. The $j$-th integer in the $i$-th line is $A_{i,j}$.

Note: All values $A_{i,j}$ are distinct.

outputFormat

Output a single integer representing the number of subrectangles of the grid for which the unique decreasing order (when sorted by height in descending order) yields a valid path (i.e. every consecutive pair of cells in this order are adjacent).

sample

2 2
4 1
3 2

3