题目描述

19 世纪初，统治者下令在俯瞰美丽河景的高原上建造一座宫殿。这块高原被看做是一个由正方形单元格组成的 $n \times m$ 网格。网格的行从 $0$ 到 $n-1$ 编号，列从 $0$ 到 $m-1$ 编号。第 $i$ 行第 $j$ 列（$0 \le i \le n - 1, 0 \le j \le m - 1$）的单元格记为单元格 $(i, j)$。每个单元格 $(i, j)$ 有特定的海拔高度，记为 $a[i][j]$。

统治者指示他的建筑师选择一个矩形区域来建造宫殿。该区域不能包含网格边界（第 $0$ 行，第 $n-1$ 行，第 $0$ 列，以及第 $m-1$ 列）上的任何单元格。为此，建筑师应选出四个整数 $r_1$，$r_2$，$c_1$ 和 $c_2$（$1 \le r_1 \le r_2 \le n - 2$ 且 $1 \le c_1 \le c_2 \le m - 2$，对应于包括所有满足 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 的单元格 $(i, j)$ 的矩形区域。

此外，一个区域被认为是合法的，当且仅当对于该区域中的每个单元格 $(i, j)$，以下条件成立：对于与该区域相邻的、位于第 $i$ 行的两个单元格（单元格 $(i, c_1-1)$ 和 $(i, c_2+1)$），以及与该区域相邻的、位于第 $j$ 列的两个单元格（单元格 $(r_1-1, j)$ 和 $(r_2+1, j)$），单元格 $(i, j)$ 的海拔高度必须严格小于这四个单元格的海拔高度。

你的任务是帮助建筑师统计可建宫殿的合法区域的数量（也就是所对应区域为合法的 $r_1, r_2, c_1$ 和 $c_2$ 的数量）。

输入格式

第一行，两个整数 $n$ 和 $m$，表示网格的长和宽。
第 $i+2$ 行（$0 \le i \le n-1$）：$m$ 个整数，为 $a[i][0], a[i][1], \cdots, a[i][m - 1]$。

输出格式

一行，一个整数，表示合法区域的数量。

6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

6

数据范围与提示

对于所有数据：

• $1 \le n, m \le 2500$
• $0 \le a[i][j] \le 7\ 000\ 000$（$0 \le i \le n - 1, 0 \le j \le m - 1$）

详细子任务附加限制与分值如下表：