Долини

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

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

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

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

• Набір клітинок називається "реберно-суміжним", якщо можна дістатися до будь-якої клітинки набору з будь-якої іншої, рухаючись вгору, вниз, вліво або вправо.

• Набір клітинок називається "точково-суміжним", якщо можна дістатися до будь-якої клітинки набору з будь-якої іншої, рухаючись вгору, вниз, вліво, вправо або по діагоналі.

• "Регіон" - це непорожній набір прилеглих один до одного реберно-суміжних клітинок.

• Регіон називається "дірявим", якщо його доповнення (включаючи нескінченні клітинки за межами сітки n * n) не є точково-суміжним.

• "Границя" області - це набір клітинок, які ортогонально суміжні (вгору, вниз, вліво або вправо) з деякою клітинкою в регіоні, але не належать самому регіону.

• "Долина" - це будь-яка область без дірок, у якій кожна клітинка має висоту нижчу, ніж кожна клітинка на границі області.

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

Приклади

Це регіон:

oo.
ooo
..o

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

oo.
oo.
..o

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

ooo
o..
o..

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

ooo
o.o
ooo

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

ooo
o.o
oo.

Вхідні дані

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

Вихідні дані

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

Приклад

У цьому прикладі три долини розміру 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.

Приклади