题目描述

题目来自 $USACO$ $2019$ $US$ $Open$ $Contest$, $Platinum$ $Problem$ $3$. Valleys

Bessie 喜欢观光，而今天她正在寻找景色优美的山谷。

她感兴趣的是一个 $N \times N$ 的方阵，其中每个格子都有一个高度。所有在此正方形方阵之外的格子的高度可以被看作是无限大。

山谷指的是一块连续、不含洞的一块区域，并且每个相邻的包围该区域的格子都高于这块区域中的所有格子。

更形式化地说：

• 一组格子被称作是「沿边相邻」的，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右方向的移动，到达其中所有其他格子。
• 一组格子被称作是「沿点相邻」的，如果可以从其中任意一个格子出发，经过一些沿上、下、左、右、对角线方向的移动，到达其中所有其他格子。
• 一个「区域」指的是一组非空并且沿边相邻的格子。
• 一个区域被称作是「有洞」的，如果这个区域的补集（包括在 $N \times N$ 方阵之外的无限高格子）不是沿点相邻的。
• 区域的「边界」指的是所有与该区域内的某个格子正交相邻（上、下、左、右），但本身不在该区域内的格子。
• 一个「山谷」指的是某个非有洞区域，满足区域内的任意格子的高度低于该区域边界上任意格子的高度。

Bessie 的目标是求出所有山谷的大小之和。

---

一些例子

• 这是一个区域：

oo.
ooo
..o

• 这不是一个区域（中间的格子和右下角的格子不沿边相邻）：

oo.
oo.
..o

• 这是一个非有洞区域：

ooo
o..
o..

• 这是一个有洞的区域（「甜甜圈」中间的格子与区域外的格子不沿点相邻）：

ooo
o.o
ooo

• 这是另一个非有洞区域（中间的格子与右下角的格子沿点相邻）：

ooo
o.o
oo.

---

输入格式

输入的第一行包含 $N$，其中 $1 \le N \le 750$。

以下 $N$ 行每行包含 $N$ 个整数，为方阵每个格子的高度。所有高度 $h$ 满足 $1 \le h \le 10^6$。所有高度均为不同的整数。

---

输出格式

输出一个整数，为所有山谷的大小之和。

---

样例

输入：

3
1 10 2
20 100 30
3 11 50

输出：

30

在这个例子中，有：

• 三个大小为 $1$ 的山谷
• 一个大小为 $2$ 的山谷
• 一个大小为 $3$ 的山谷
• 一个大小为 $6$ 的山谷
• 一个大小为 $7$ 的山谷
• 一个大小为 $9$ 的山谷

所以，答案为 $1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30$。

---

数据范围与提示

对于至少 $19\%$ 的测试数据，额外保证 $N \le 100$。