계곡

Bessie는 관광을 좋아한다. 오늘 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$을 만족한다. 모든 높이는 서로 다른 정수이다.

테스트 케이스의 최소 19%에서는 추가로 $N \leq 100$이 보장된다.

모든 계곡의 크기의 합을 하나의 정수로 출력한다.

이 예시에는 크기 1인 계곡이 세 개 있다:

o.o
...
o..

크기 2인 계곡이 하나 있다:

...
...
oo.

크기 3인 계곡이 하나 있다:

ooo
...
...

크기 6인 계곡이 하나 있다:

ooo
o..
oo.

크기 7인 계곡이 하나 있다:

ooo
o.o
oo.

크기 9인 계곡이 하나 있다:

ooo
ooo
ooo

따라서 답은 1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30이다.