配点: 100 点
JOI 你在海滩上玩耍并建造了沙堡。 JOI 您建造的城堡位于一个带有沙滩的矩形区域内。这个矩形区域是垂直的 H 行,横 W 表示为分为列的网格,垂直方向平行于南北方向,水平方向平行于东西方向。从北方 i 行目 (1 \leqq i \leqq H),从西边 正方形 j 列目 (1 \leqq j \leqq W的高度是 A_{i, j} 。但是,A_{i, j} 的值都不同。
JOI 对这座沙堡执行了以下操作。
- 选择一个方格并从该方格上方开始。
- 之后,北、南、东、西相邻降低要移动到一个正方形上, 重复至少0 次。
最后,JOI 如果你从上面看一下你访问过的广场的面积,这是 1 由两个矩形表示。
每个方块的高度 给定信息 A_{i, j} ,编写一个程序来查找 JOI 访问的正方形中可能存在的矩形区域的数量。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}
出力
标准输出显示 JOI 访问的正方形有多少个可能的矩形区域。1 行。
制約
- H \geqq 1.
- W \geqq 1.
- H \times W \leqq 50\,000.
- 1 \leqq A_{i, j} \leqq 10\,000\,000 (1 \leqq i \leqq H,1 \leqq j \leqq W).
- A_{i_1, j_1} \neq A_{i_2, j_2} (1 \leqq i_1 \leqq H,1 \leqq j_1 \leqq W,1 \leqq i_2 \leqq H,1 \leqq j_2 \leqq W,(i_1, j_1) \neq (i_2, j_2)).
小課題
- (9 点) H = 1.
- (10 点) H \times W \leqq 100.
- (5 点) H \times W \leqq 1\,500.
- (56 点) H \times W \leqq 7\,000.
- (20 点)没有额外的限制。
入力例 1
1 5 2 4 7 1 5
出力例 1
10
JOI 以下是您访问过的广场的矩形区域。 10 既然有一条可能的街道,10 。 您将获得

入力例 2
3 2 18 10 19 12 17 13
出力例 2
15
JOI 以下是您访问过的广场的矩形区域。 15 既然有一条可能的街道,15 。 您将获得

此输入示例是一个小作业。 2, 3, 4, 5 满足约束。
入力例 3
3 5 83 47 36 38 40 13 10 26 68 67 15 19 20 70 90
出力例 3
65
例如,考虑以下矩形区域。包括其他一切在内,总计 65 因为有65 。 您将获得

此输入示例是一个小作业。 2, 3, 4, 5 满足约束。