题目描述

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 5
2 4 7 1 5

10

3 2
18 10
19 12
17 13

15

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

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 T5「砂の城 2 / Sandcastle 2」