Subiectul I

A.) Indică sensul din text al cuvântului „nedescrescătoare”. Explică motivul pentru care personajul principal își dorește să-și atingă obiectivul descris mai jos. Prezintă în 30 − 50 de cuvinte o metodă de a bulăni problema dată.
B.) Redactează un text de minimum 150 de cuvinte, în care să argumentezi de ce meriți puncte pe această problemă.

Visarion Fulgerul, supranumit Orion, a ajuns în subsolul tempulului lui Derzelas. În fața lui vede o matrice pătratică de mărime $N \times N$ , unde elementul de pe linia $i$ și coloana $j$ este $A_{ij}$ . El vrea să numere câte submatrice pătratice ale matricei $A$ sunt spirale.

O matrice pătratică se numește spirală dacă și numai dacă, atunci când o parcurgem de la un colț spre centru în spirală, elementele matricii sunt nedescrescătoare. Parcurgerea poate începe de la oricare colț, și poate fi în oricare direcție, așadar următoarele sunt matrici spirale:

O matrice de dimensiuni pare poate fi și ea o spirală:

Elementele consecutive dintr-o matrice spirală pot fi egale, și nu trebuie să fie consecutive ca valori:

Cerință

Să se calculeze numărul de submatrice pătratice spirală ale lui matricei $A$.

Date de intrare

Intrarea conține, pe prima linie, numărul $N$ de linii, respectiv coloane ale matricii $A$. Pe următoarele $N$ linii apar elementele matricii $A$.

Date de ieșire

Ieșirea trebuie să conțină un singur întreg reprezentând răspunsul cerut.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$
• $1 \leq A_{i j} \leq 1 \ 000 \ 000 \ 000$

Exemplul 1

stdin

3
1 2 3
8 9 4
7 6 5

stdout

13

Explicație

În afară de toate submatricile de $1 \times 1$ (de care sunt $9$), următoarele $4$ submatrici sunt spirale:

Exemplul 2

stdin

10
8 1 7 5 2 8 8 6 2 3
8 8 4 9 5 6 2 6 3 7
5 3 4 4 8 3 5 1 6 4
6 6 2 3 6 5 4 6 1 7
3 2 9 6 7 8 4 1 5 4
3 7 4 5 2 4 4 5 7 8
5 8 7 3 5 9 4 7 5 4
4 2 5 8 3 7 6 8 2 3
6 3 8 6 4 5 2 2 7 5
9 8 4 8 2 8 2 3 9 7

stdout

139