Долины

Бесси любит осматривать достопримечательности, и сегодня она ищет живописные долины.

Ее интересует сетка 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.

Примеры