一个晴朗的一天,萨莎去公园散步。在公园里,他看到他最喜欢的长凳被占用了,他只好坐在旁边的长凳上。他坐下来,开始聆听寂静。突然,他想到了一个问题:如果在公园的不同地方,寂静的声音有不同的表现呢?确实如此。我们将公园划分为 $$$1 \times 1$$$ 平方米,并将其称为单元格,并从上到下编号从 $$$1$$$ 到 $$$n$$$ 的行,从左到右编号从 $$$1$$$ 到 $$$m$$$ 的列。现在,每个单元格都可以用一对两个整数 $$$(x, y)$$$ 来描述,其中 $$$x$$$ — 行号,$$$y$$$ — 列号。 Sasha 知道单元格 $$$(i, j)$$$ 中的静音级别等于 $$$f_{i,j}$$$,并且所有 $$$f_{i,j}$$$ 形成从 $$$1$$$ 到 $$$n \cdot m$$$ 的数字排列。萨莎决定数一数,有多少令人愉快的沉默片段?
让我们看一些段$$$[l \ldots r]$$$。将$$$S$$$ 表示为$$$l \le f_{i,j} \le r$$$ 的单元格集合$$$(i, j)$$$。然后,如果来自 $$$S$$$ 的每对单元格之间只有一条简单路径(路径不能包含不在 $$$S$$$ 中的单元格),那么这段沉默 $$$[l \ldots r]$$$ 是令人愉快的。换句话说,集合 $$$S$$$ 应该看起来像平原上的一棵树。萨莎很快就完成了这项任务,并将该算法称为“沉默的声音算法”。
时间过去了,算法唯一留下的只是一个传说。为了证明这个故事的真实性,你必须帮助萨沙并找出不同的愉快的沉默片段的数量。如果 $$$l_1 \neq l_2$$$ 或 $$$r_1 \neq r_2$$$ 或两者同时存在,则两个段 $$$[l_1 \ldots r_1]$$$、$$$[l_2 \ldots r_2]$$$ 不同。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 1000$$$, $$$1 \le n \cdot m \le 2 \cdot 10^5$$$) — 公园的大小。
接下来的 $$$n$$$ 行中的每一行都包含 $$$m$$$ 整数 $$$f_{i,j}$$$ ($$$1 \le f_{i,j} \le n \cdot m$$$) — 编号为 $$$(i, j)$$$ 的单元格中的静音级别。
保证所有 $$$f_{i,j}$$$ 都是不同的。
输出
打印一个整数——愉快的沉默片段的数量。
示例
输入 #1
1 5 1 2 3 4 5
输出 #1
15
输入 #2
2 3 1 2 3 4 5 6
输出 #2
15
输入 #3
4 4 4 3 2 16 1 13 14 15 5 7 8 12 6 11 9 10
输出 #3
50
注意
在第一个例子中,所有的沉默片段都是令人愉快的。
在第二个示例中,愉快的沉默片段如下: