Bessie thích ngắm cảnh, và hôm nay cô đang tìm kiếm những thung lũng đẹp.

Ta xét một lưới ô vuông \(N \times N\), trong đó mỗi ô có một độ cao. Mọi ô nằm ngoài lưới vuông này có thể được coi là có độ cao vô hạn.

Một thung lũng là một vùng của lưới liên thông, không có lỗ và có tính chất mọi ô kề ngay xung quanh nó đều cao hơn tất cả các ô trong vùng.

Cụ thể hơn:

• Một tập hợp các ô được gọi là liên thông theo cạnh nếu có thể đi từ bất kỳ ô nào trong tập tới bất kỳ ô nào khác bằng một chuỗi bước đi lên, xuống, sang trái hoặc sang phải.
• Một tập hợp các ô được gọi là liên thông theo điểm nếu có thể đi từ bất kỳ ô nào trong tập tới bất kỳ ô nào khác bằng một chuỗi bước đi lên, xuống, sang trái, sang phải hoặc theo đường chéo.
• Một vùng là một tập hợp ô không rỗng và liên thông theo cạnh.
• Một vùng được gọi là có lỗ nếu phần bù của vùng (bao gồm vô số ô nằm ngoài lưới \(N \times N\)) không liên thông theo điểm.
• Biên của một vùng là tập hợp các ô kề theo cạnh (phía trên, dưới, trái hoặc phải) với một ô nào đó trong vùng nhưng không thuộc chính vùng đó.
• Một thung lũng là bất kỳ vùng không có lỗ nào sao cho mọi ô trong vùng đều có độ cao thấp hơn mọi ô trên biên của vùng.

Mục tiêu của Bessie là xác định tổng kích thước của tất cả các thung lũng.

Các minh họa

Đây là một vùng:

oo.
ooo
..o

Đây không phải là một vùng (ô ở giữa và ô ở góc dưới bên phải không liên thông theo cạnh):

oo.
oo.
..o

Đây là một vùng không có lỗ:

ooo
o..
o..

Đây là một vùng có lỗ (ô duy nhất nằm bên trong hình "bánh vòng" không liên thông theo điểm với phần "bên ngoài" của vùng):

ooo
o.o
ooo

Đây là một vùng không có lỗ khác (ô duy nhất ở chính giữa liên thông theo điểm với ô ở góc dưới bên phải):

ooo
o.o
oo.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), với \(1 \le N \le 750\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên là độ cao của các ô trong lưới. Mỗi độ cao \(h\) thỏa mãn \(1 \le h \le 10^6\). Mọi độ cao đều là các số nguyên phân biệt.

Phân nhóm

• Trong ít nhất 19% số trường hợp kiểm thử, đảm bảo thêm rằng \(N \leq 100\).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng kích thước của tất cả các thung lũng.

Ví dụ

3
1 10 2
20 100 30
3 11 50

30

o.o
...
o..

...
...
oo.

ooo
...
...

ooo
o..
oo.

ooo
o.o
oo.

ooo
ooo
ooo

Nguồn

USACO 2019 US Open Contest, Platinum — Valleys

Tác giả: Travis Hance.