subpermutari

Subpermutari

== include(page="template/taskheader" task_id="subpermutari") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $subpermutari.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $subpermutari.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 2000$

h2. Exemplu
table(example). |_. subpermutari.in |_. subpermutari.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
1 3 2 4
| 24

|
h3. 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.
 

== include(page="template/taskfooter" task_id="subpermutari") ==