Counting Valid Palace Regions

In the early 19th century, a ruler ordered a palace to be built on a high plateau overlooking a beautiful river. The plateau is modeled as an \(n \times m\) grid of square cells. The rows are numbered from \(0\) to \(n-1\) and the columns from \(0\) to \(m-1\). The cell in row \(i\) and column \(j\) (\(0 \le i \le n-1\) and \(0 \le j \le m-1\)) is denoted by \((i,j)\), and its altitude is given as \(a_{i,j}\>.

The ruler instructed his architect to choose a rectangular region (composed of contiguous cells) for the palace. The region cannot include any cell on the grid boundary (i.e. the 0-th row, the \((n-1)\)-th row, the 0-th column, or the \((m-1)\)-th column). Therefore, the architect must choose four integers \(r_1\), \(r_2\), \(c_1\) and \(c_2\) satisfying

[ 1 \le r_1 \le r_2 \le n-2 \quad\text{and}\quad 1 \le c_1 \le c_2 \le m-2 ]

such that the rectangle covers all cells ((i,j)) with (r_1 \le i \le r_2) and (c_1 \le j \le c_2>.

Moreover, a region is considered legal if and only if for every cell \((i,j)\) in the region, the following condition holds: Let the four cells adjacent to the region be

• the cell in row \(i\) immediately to the left of the region: \((i, c_1-1)\),
• the cell in row \(i\) immediately to the right of the region: \((i, c_2+1)\),
• the cell in column \(j\) immediately above the region: \((r_1-1, j)\),
• and the cell in column \(j\) immediately below the region: \((r_2+1, j)\).

Then for every ((i,j)) in the region it must be true that

[ a_{i,j} < a_{i, c_1-1},\quad a_{i,j} < a_{i, c_2+1},\quad a_{i,j} < a_{r_1-1,j},\quad a_{i,j} < a_{r_2+1,j}. ]

Your task is to help the architect count the number of legal rectangular regions (i.e. the number of quadruples \((r_1,r_2,c_1,c_2)\) that yield a legal region).

inputFormat

The first line contains two integers \(n\) and \(m\) (\(n,m \ge 4\)). Each of the next \(n\) lines contains \(m\) integers. The \(j\)-th integer in the \(i\)-th line represents \(a_{i,j}\), the altitude of cell \((i,j)\).

outputFormat

Output a single integer, the number of legal rectangular regions for the palace.

sample

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

4