P14701 [ICPC 2024 Tehran R] Parking Theory

设拉子大学有一个长方形的停车场，拥有 $n \times m$ 个停车位。停车场的每一行和每一列的两端都有入口。 停车场已停满，每个停车位上的汽车进入顺序已给出。具体而言，标有数字 $1$ 的单元格是第一个进入停车场的汽车，标有数字 $n \cdot m$ 的单元格是最后一个进入的。 Abolfazl 有一个关于汽车如何在该停车场停放的理论。他认为，任何从特定一侧（行或列）进入停车场的汽车都会直线行驶，直到找到其停车位，并且从不改变方向。此外，汽车不能穿过已停有汽车的单元格。 Abolfazl 想要计算停车场中满足此条件的子网格数量。一个子网格是有效的，如果仅考虑该子网格内的汽车，它们都能在不违反上述规则的情况下停放。 请帮助 Abolfazl 确定这样的有效子网格的数量。

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \leq n, m \leq 500$)，表示停车场的行数和列数。接下来的 $n$ 行每行包含 $m$ 个整数，表示汽车的进入顺序。保证数字是 $1$ 到 $n \cdot m$ 之间的不同整数。

输出一个整数，表示停车场中有效子网格的数量。

翻译由 DeepSeek V3 完成