Fișierul intrare/ieșire	ssdj.in, ssdj.out	Sursă	Lot Sovata 2014
Autor	Adrian Panaete | Dan Pracsiu | Vlad Gavrilă	Adăugată de	Radu Muntean • heracle
Timp de execuție pe test	1 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	5

Vezi soluțiile trimise | Statistici

Ssdj (lot liceu)

Pentru că nu au luat toți nota 10 la simulare, conducerea liceului a hotărât să pedepsească elevii într-un mod inuman: aceștia nu au mai avut voie să meargă la teatru și nici să mai citească din marii clasici ai literaturii. Singura lor mângâiere era o matrice cu N linii și N coloane care conține numai litere mici ale alfabetului englez, pentru care trebuiau să identifice submatricele valabile. O submatrice este considerată valabilă dacă îndeplinește simultan următoarele condiții:

• are cel puțin două linii și cel puțin două coloane;
• literele aflate în colțurile stânga-sus și dreapta-jos ale submatricei sunt strict mai mari lexicografic decât toate celelalte litere din submatrice.

Ajutați elevii liceului să afle numărul submatricelor valabile care există în matrice și să scape astfel de pedeapsa îngrozitoare.

Date de intrare

Fișierul ssdj.in conține pe prima linie numărul natural N, iar pe următoarele N linii se află câte N litere mici, neseparate prin spații.

Date de ieșire

Fișierul ssdj.out conține un singur număr natural reprezentând numărul de submatrice valabile.

Restricții

• 1 ≤ N ≤ 1000
• Pentru teste valorând 10 puncte, N ≤ 50.
• Pentru teste valorând 20 puncte, matricea va conține numai literele a și b.

Exemplu

ssdj.in	ssdj.out
4 maea bcda aaae aaaa	3

Explicație

Submatricele valabile sunt:

1)
ma
bc

2)
ea
da
ae

3)
da
ae