CF1109F.Sasha and Algorithm of Silence's Sounds

One fine day Sasha went to the park for a walk. In the park, he saw that his favorite bench is occupied, and he had to sit down on the neighboring one. He sat down and began to listen to the silence. Suddenly, he got a question: what if in different parts of the park, the silence sounds in different ways? So it was. Let's divide the park into $1 \times 1$ meter squares and call them cells, and numerate rows from $1$ to $n$ from up to down, and columns from $1$ to $m$ from left to right. And now, every cell can be described with a pair of two integers $(x, y)$, where $x$ — the number of the row, and $y$ — the number of the column. Sasha knows that the level of silence in the cell $(i, j)$ equals to $f_{i,j}$, and all $f_{i,j}$ form a permutation of numbers from $1$ to $n \cdot m$. Sasha decided to count, how many are there pleasant segments of silence?

Let's take some segment $[l \ldots r]$. Denote $S$ as the set of cells $(i, j)$ that $l \le f_{i,j} \le r$. Then, the segment of silence $[l \ldots r]$ is pleasant if there is only one simple path between every pair of cells from $S$ (path can't contain cells, which are not in $S$). In other words, set $S$ should look like a tree on a plain. Sasha has done this task pretty quickly, and called the algorithm — "algorithm of silence's sounds".

Time passed, and the only thing left from the algorithm is a legend. To prove the truthfulness of this story, you have to help Sasha and to find the number of different pleasant segments of silence. Two segments $[l_1 \ldots r_1]$, $[l_2 \ldots r_2]$ are different, if $l_1 \neq l_2$ or $r_1 \neq r_2$ or both at the same time.

一个晴朗的日子，萨沙去公园散步。在公园里，他发现他最喜欢的长椅已被占用，只好坐在旁边的长椅上。他坐下来，开始聆听寂静。突然，他产生了一个疑问：公园不同区域的“寂静”听起来会不会有所不同？事实的确如此。让我们将公园划分为 $1 \times 1$ 米的正方形小格，并称其为“单元格”；行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。此时，每个单元格可用一对整数 $(x, y)$ 表示，其中 $x$ 表示行号，$y$ 表示列号。萨沙知道单元格 $(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)$ 组成的集合。那么，寂静区间 $[l \ldots r]$ 被称为“悦耳的”，当且仅当集合 $S$ 中任意两个单元格之间仅存在唯一一条简单路径（该路径不允许经过不属于 $S$ 的单元格）。换言之，集合 $S$ 在平面上应构成一棵树。萨沙很快完成了这一任务，并将该算法命名为——“寂静之声算法”。

时光流逝，该算法仅余传说。为证实这个故事的真实性，你需要帮助萨沙，求出不同的悦耳寂静区间的数量。若两个区间 $[l_1 \ldots r_1]$ 与 $[l_2 \ldots r_2]$ 满足 $l_1 \neq l_2$ 或 $r_1 \neq r_2$（或两者同时成立），则它们被视为不同的区间。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1000$, $1 \le n \cdot m \le 2 \cdot 10^5$) — the size of the park.

Each from next $n$ lines contains $m$ integers $f_{i,j}$ ($1 \le f_{i,j} \le n \cdot m$) — the level of silence in the cell with number $(i, j)$.

It is guaranteed, that all $f_{i,j}$ are different.

第一行包含两个整数 $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}$ 均互不相同。

Print one integer — the number of pleasant segments of silence.

输出一个整数——表示悦耳的静音区段的数量。

In the first example, all segments of silence are pleasant.

In the second example, pleasant segments of silence are the following:

在第一个例子中，所有静音段都是令人愉悦的。

在第二个例子中，令人愉悦的静音段如下所示：