Dərələr

Bessi görməli yerləri gəzməyi sevir və bu gün o, mənzərəli vadilər axtarır.

O, n * n ölçülü bir şəbəkə ilə maraqlanır, burada hər bir hüceyrənin müəyyən bir hündürlüyü var. Şəbəkənin kənarındakı hər bir hüceyrənin sonsuz hündürlükdə olduğunu qəbul edə bilərik.

Vadi, şəbəkənin müəyyən bir sahəsidir ki, bu sahə bitişikdir, deşikləri yoxdur və onu əhatə edən hər bir hüceyrə bu sahədəki bütün hüceyrələrdən daha yüksəkdir.

Daha dəqiq desək:

• Hüceyrələr dəsti "kənar-bitişik" adlanır, əgər hər hansı bir hüceyrəyə digərindən yuxarı, aşağı, sola və ya sağa hərəkət etməklə çatmaq mümkündürsə.

• Hüceyrələr dəsti "nöqtə-bitişik" adlanır, əgər hər hansı bir hüceyrəyə digərindən yuxarı, aşağı, sola, sağa və ya diaqonal hərəkət etməklə çatmaq mümkündürsə.

• "Region" - bu, kənar-bitişik hüceyrələrin boş olmayan bir dəstidir.

• Region "deşikli" adlanır, əgər onun tamamlayıcısı (bu, n * n şəbəkəsinin kənarındakı sonsuz hüceyrələri də əhatə edir) nöqtə-bitişik deyilsə.

• Sahənin "sərhədi" - bu, regiondakı bəzi hüceyrələrlə ortoqonal bitişik (yuxarı, aşağı, sola və ya sağa) olan, lakin sahənin özündə olmayan hüceyrələr dəstidir.

• "Vadi" - bu, deşiksiz olan və hər bir hüceyrəsi sahənin sərhədindəki hər bir hüceyrədən daha aşağı olan hər hansı bir sahədir.

Bessinin vəzifəsi bütün vadilərin ölçülərinin cəmini tapmaqdır.

Nümunələr

Bu bir regiondur:

oo.
ooo
..o

Bu region deyil (orta hüceyrə və aşağı sağ hüceyrə kənar-bitişik deyil):

oo.
oo.
..o

Bu deşiksiz bir regiondur:

ooo
o..
o..

Bu deşikli bir sahədir (halqa formasında olan ayrı hüceyrə sahənin "xarici tərəfi" ilə nöqtə-bitişik deyil):

ooo
o.o
ooo

Bu, deşiksiz başqa bir sahədir (mərkəzdəki hüceyrə sağ alt küncdəki hüceyrə ilə nöqtə-bitişikdir):

ooo
o.o
oo.

Giriş məlumatları

Birinci sətir tam ədəd n (1 ≤ n ≤ 750) ehtiva edir. Növbəti n sətirin hər biri şəbəkənin hüceyrələrinin hündürlüyünü ehtiva edən n tam ədəd ehtiva edir. Hər bir hündürlük h şərtini ödəyir 1 ≤ h ≤ 10^6. Bütün hündürlüklər fərqli tam ədədlərdir.

Çıxış məlumatları

Tək tam ədəd çıxarın - bütün vadilərin ölçülərinin cəmi.

Nümunə

Bu nümunədə üç vadi ölçüsü 1:

o.o
...
o..

Bir vadi ölçüsü 2:

...
...
oo.

Bir vadi ölçüsü 3:

ooo
...
...

Bir vadi ölçüsü 6:

ooo
o..
oo.

Bir vadi ölçüsü 7:

ooo
o.o
oo.

Bir vadi ölçüsü 9:

ooo
ooo
ooo

Beləliklə, cavab 1 + 1 + 1 + 2 + 3 + 6 + 7 + 9 = 30.