题目描述

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$，表示网格的长和宽。

接下来 $n$ 行，第 $i$ 行 $m$ 个整数，为 $a_{i-1,0\dots 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

提示

样例解释

一共有 $6$ 个合法区域，分别为：

• $r_1=r_2=1, c_1=c_2=1$
• $r_1=1, r_2=2, c_1=c_2=1$
• $r_1=r_2=1, c_1=c_2=3$
• $r_1=r_2=4, c_1=2,c_2=3$
• $r_1=r_2=4, c_1=c_2=3$
• $r_1=3,r_2=4,c_1=c_2=3$

例如，$r_1=1, r_2=2, c_1=c_2=1$ 对应一个合法区域，原因是以下两个条件都成立：

• $a_{1,1}=4$ 严格小于 $a_{0,1}=8$，$a_{3,1}=14$，$a_{1,0}=7$，和 $a_{1,2}=10$。
• $a_{2,1}=7$ 严格小于 $a_{0,1}=8$，$a_{3,1}=14$，$a_{2,0}=9$，和 $a_{2,2}=20$。

数据范围

对于所有数据：

• $1 \le n, m \le 2500$。
• $0 \le a_{i,j} \le 7 \times 10^6 (0 \le i \le n - 1, 0 \le j \le m - 1)$。

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