JOI-kun 正在沙滩上玩耍。他堆了一个沙堡。JOI-kun 堆的沙堡位于沙滩上的一个矩形区域内。该矩形区域由 $H$ 行 $W$ 列的单元格组成。从北向南第 $i$ 行（$1 \le i \le H$）且从西向东第 $j$ 列（$1 \le j \le W$）的单元格高度为 $A_{i,j}$。注意，所有 $A_{i,j}$ 的值互不相同。

JOI-kun 对沙堡进行了以下操作： 1. 首先，JOI-kun 选择了一个单元格，并从该单元格开始移动。 2. 然后，他从当前单元格移动到四个方向之一的相邻单元格。他必须移动到比当前单元格高度低的单元格。他重复此过程零次或多次。

最后，如果我们从上方观察他访问过的单元格，这些单元格形成了一个矩形。

给定每个单元格的高度 $A_{i,j}$，编写一个程序，计算 JOI-kun 访问过的单元格所能形成的矩形的数量。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$H \ W$ $A_{1,1} \ A_{1,2} \ \dots \ A_{1,W}$ $A_{2,1} \ A_{2,2} \ \dots \ A_{2,W}$ $\vdots$ $A_{H,1} \ A_{H,2} \ \dots \ A_{H,W}$

输出格式

向标准输出打印一行。输出应包含 JOI-kun 访问过的单元格所能形成的矩形的数量。

数据范围

• $H \ge 1$
• $W \ge 1$
• $H \times W \le 50\,000$
• $1 \le A_{i,j} \le 10\,000\,000$ ($1 \le i \le H, 1 \le j \le W$)
• $A_{i_1,j_1} \neq A_{i_2,j_2}$ ($1 \le i_1 \le H, 1 \le j_1 \le W, 1 \le i_2 \le H, 1 \le j_2 \le W, (i_1, j_1) \neq (i_2, j_2)$)

子任务

1. (9 分) $H = 1$
2. (10 分) $H \times W \le 100$
3. (5 分) $H \times W \le 1\,500$
4. (56 分) $H \times W \le 7\,000$
5. (20 分) 无附加限制

样例

输入格式 1

1 5
2 4 7 1 5

输出格式 1

10

说明

由于 JOI-kun 访问过的单元格可以形成 10 种可能的矩形，因此输出 10。

输入格式 2

3 2
18 10
19 12
17 13

输出格式 2

15

说明

由于 JOI-kun 访问过的单元格可以形成 15 种可能的矩形，因此输出 15。

输入格式 3

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

输出格式 3

65

说明

例如，JOI-kun 访问过的单元格可以形成以下矩形。由于总共有 65 种可能的矩形，因此输出 65。