[JOI 2022 Final] 沙堡 2 (Sandcastle 2)
题目描述
JOI 君在沙滩上玩耍。他建造了一座沙堡。这座由 JOI 君建造的沙堡位于沙滩上的一个矩形区域内。这个矩形区域有 $H$ 行 $W$ 列。位于从上往下的第 $i$ 行、从左往右的第 $j$ 列的格子的高度为 $A_{i, j}$。**注意所有 $\boldsymbol{A_{i, j}}$ 的值互不相同。**
在沙堡上，JOI 君执行了下列动作。
1. 首先，JOI 君选择一个格子，他从该格子开始移动。
2. 然后，他从当前格子出发朝上下左右四个方向之一移动到相邻的格子上。他必须移动到低于当前格子的格子上。他可以重复此动作零次或更多次。
最终，如果我们从上往下看，他经过的格子将形成一个矩形。
给定每个格子的高度信息 $A_{i, j}$，写一个程序计算所有可能的由 JOI 君经过的格子组成的矩形的数量。
输入输出格式
输入格式
第一行，两个正整数 $H, W$。
接下来 $H$ 行，第 $i$ 行 $W$ 个正整数 $A_{i, 1}, A_{i, 2}, \ldots, A_{i, W}$。
输出格式
输出一行，一个数，表示所有可能的由 JOI 君经过的格子组成的矩形的数量。
输入输出样例
输入样例 #1
1 5
2 4 7 1 5
输出样例 #1
10
输入样例 #2
3 2
18 10
19 12
17 13
输出样例 #2
15
输入样例 #3
3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90
输出样例 #3
65
说明
**【样例解释 \#1】**
由于有 $10$ 个可能的由 JOI 君经过的格子组成的矩形，输出 $10$。
这个样例满足所有子任务的限制。
**【样例解释 \#2】**
由于有 $15$ 个可能的由 JOI 君经过的格子组成的矩形，输出 $15$。
这个样例满足子任务 $2, 3, 4, 5$ 的限制。
**【样例解释 \#3】**
举个例子，如下矩形可以由 JOI 君经过的格子组成。由于总共有 $65$ 个可能的矩形，输出 $65$。
这个样例满足子任务 $2, 3, 4, 5$ 的限制。
----
**【数据范围】**
**本题采用捆绑测试。**
对于 $100 \%$ 的数据，$1 \le H, W, H \cdot W \le 5 \times {10}^4$，$1 \le A_{i, j} \le {10}^7$，$A_{i_1, j_1} \ne A_{i_2, j_2}$（$(i_1, j_1) \ne (i_2, j_2)$）。
- 子任务 $1$（$9$ 分）：$H = 1$。
- 子任务 $2$（$10$ 分）：$H \cdot W \le 100$。
- 子任务 $3$（$5$ 分）：$H \cdot W \le 1500$。
- 子任务 $4$（$56$ 分）：$H \cdot W \le 7000$。
- 子任务 $5$（$20$ 分）：无特殊限制。
----
**译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T5「[砂の城 2 ](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t5.pdf) / [Sandcastle 2](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t5-en.pdf)」**