题目描述

译自 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 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

数据范围

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