Долини#10327

Долини

1 секунда

128 мегабайтів

Дуже складна

Бессі захоплюється оглядом визначних місць, і сьогодні вона шукає мальовничі долини.

Її цікавить сітка розміром $n \times n$ n \times n клітинок, де кожна клітинка має певну висоту. Вважається, що кожна клітинка за межами цієї квадратної сітки має нескінченну висоту.

Долина - це область сітки, яка є суміжною, без дірок, і така, що кожна клітинка, яка безпосередньо оточує її, має висоту більшу, ніж усі клітинки в цій області.

Більш формально:

Набір клітинок називається "реберно-суміжним", якщо можна дістатися до будь-якої клітинки набору з будь-якої іншої, рухаючись вгору, вниз, вліво або вправо.
Набір клітинок називається "точково-суміжним", якщо можна дістатися до будь-якої клітинки набору з будь-якої іншої, рухаючись вгору, вниз, вліво, вправо або по діагоналі.
"Регіон" - це непорожній набір прилеглих один до одного реберно-суміжних клітинок.
Регіон називається "дірявим", якщо його доповнення (включаючи нескінченні клітинки за межами сітки $n \times n$ n \times n) не є точково-суміжним.
"Границя" області - це набір клітинок, які ортогонально суміжні (вгору, вниз, вліво або вправо) з деякою клітинкою в регіоні, але не належать самому регіону.
"Долина" - це будь-яка область без дірок, у якій кожна клітинка має висоту нижчу, ніж кожна клітинка на границі області.

Завдання Бессі - визначити суму розмірів усіх долин.

Приклади

Це регіон:

oo.
ooo
..o

Це не регіон (середня клітинка і нижня права клітинка не є суміжними по краях):

oo.
oo.
..o

Це регіон без дірок:

ooo
o..
o..

Це область з діркою (окрема клітинка у формі "бублика" не є точково-суміжною з "зовнішньою стороною" області):

ooo
o.o
ooo

Це ще одна область без дірок (клітинка в центрі точково прилягає до клітинки в правому нижньому куті):

ooo
o.o
oo.

Вхідні дані

Перший рядок містить ціле число $n$ ( $1 \leq n \leq 750$ 1 \le n \le 750). Кожен з наступних $n$ рядків містить $n$ цілих чисел - висоти клітинок сітки. Кожна висота $h$ задовольняє умові $1 \leq h \leq 1 0^{6}$ 1 \le h \le 10^6. Всі висоти - різні цілі числа.

Вихідні дані

Виведіть єдине ціле число - суму розмірів усіх долин.

Приклади

Приклад 1

Примітка

У цьому прикладі три долини розміру $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$ 1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30.