Fişierul intrare/ieşire:	subpermutari.in, subpermutari.out	Sursă	ONIS 2016 Runda Online
Autor	Eugenie Daniel Posdarascu	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.75 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Subpermutari

Fie P o permutare de lungime N. Spunem ca o alta permutare R (de lungime M ≤ N) este o subpermutare a lui P pe pozitia i ( i ≤ N - M + 1 ) daca oricare ar fi j si k intre 1 si M cu j ≠ k si R[j] < R[k] atunci P[j + i - 1] < P[k + i - 1].
De exemplu permutarea 1 2 este o subpermutare a lui 1 3 2 4 pe pozitiile 1 si 3.

Voua vi se da o permutare P si vi se cere pentru fiecare permutare R care apare cel putin o data ca subpermutare in P să-i contorizaţi frecvenţa apariţiilor în P. Pentru simplititate vi se cere suma patratelor acestor numere.

Date de intrare

Fişierul de intrare subpermutari.in va contine pe prima linie N, marimea permutarii P.
Urmatorul rand va contine N valori distincte intre 1 si N, separate prin spatiu, elementele permutarii.

Date de ieşire

În fişierul de ieşire subpermutari.out trebuie sa se afle un singur număr, cel cerut in cerinta problemei.

Restricţii

• 1 ≤ N ≤ 2000

Exemplu

Explicaţie

Urmatoarele subpermutari apar in P:

• 1 -> pe pozitiile 1 2 3 si 4
• 1 2 -> pe pozitiile 1 si 3
• 2 1 -> pe pozitia 2
• 1 3 2 -> pe pozitia 1
• 2 1 3 -> pe pozitia 2
• 1 3 2 4 -> pe pozitia 1

Numarul de aparitii la aceste subpermutari este 4, 2, 1, 1, 1 si 1.
Raspunsul este 4 * 4 + 2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 + 1 * 1 = 24.

Cum se trimit solutii?