题目描述
译自 JOI 2022 Final T5「砂の城 2 / Sandcastle 2」

JOI 君在沙滩上堆沙堡，他已经做好了一个沙堡，沙堡可以使用一个 $H\times W$ 的二维矩形表示，其被划分成若干个 $1\times 1$ 的小格子，格子高度互相不同。

JOI 君决定在沙堡上游走，他可以从任意一个点出发，向上下左右四个方向行走，必须满足他行走的路径单调下降。

出于一些原因，JOI 君想知道，在他所有可能的行走路径中，恰好覆盖了一个子矩形的路径数有多少条。

---

输入格式
第一行两个整数 $H,W$。
接下来 $H$ 行，一行 $W$ 个数字 $A_{i,j}$ 表示 $(i,j)$ 这个格子的高度。

输出格式
一行一个整数，表示恰好覆盖了一个子矩形的路径数有多少条。

---

样例 1
输入

1 5
2 4 7 1 5

输出

10

这个样例满足所有子任务的限制。

---

样例 2
输入

3 2
18 10
19 12
17 13

输出

15

这个样例满足子任务 $2,3,4,5$ 的限制。

---

样例 3
输入

3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90

输出

65

方案太多了，仅列举几种：

这个样例满足子任务 $2,3,4,5$ 的限制。

---

数据范围
对于全部数据，
$H,W\ge 1$，
$HW\le 5\times 10^4$，
$1\le A_{i,j}\le 10^7$，
$A_{i,j}$ 互不相同。

---

子任务

子任务	特殊限制	分值
1	$H=1$	9
2	$HW\le 100$	10
3	$HW\le 1500$	5
4	$HW\le 7000$	56
5	无特殊限制	20