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

{!>problema/copaci4?x.jpg!}
 

p<>. Se consideră $n$ copaci de diferite înălţimi, aflaţi în linie dreaptă la distanţe egale, numerotaţi de la $1$ la $n$. Pentru fiecare copac se cunoaşte înălţimea sa $H$~$i$~. Cum şi copacii simt nevoia să socializeze, fiecare dintre ei are prieteni printre ceilalţi copaci. Prietenii oricărui copac $i$ se pot afla atât la stânga, cât şi la dreapta sa. Relaţiile de prietenie sunt definite în felul următor: pentru fiecare copac $i$ considerăm un şir $d$~$1$~, $d$~$2$~, ..., $d$~$x$~ reprezentând prietenii copacului $i$ situaţi în dreapta sa şi un şir $s$~$1$~, $s$~$2$~ ... $s$~$y$~ reprezentând prietenii copacului $i$ situaţi în stânga acestuia. Copacii din cele două şiruri corespunzătoare unui copac $i$ formează împreună lista prietenilor acestuia. Şirurile corespunzătoare copacului $i$ se definesc astfel:
# • $d$~$1$~ $= i + 1$ (dacă $i = n$, atunci copacul $i$ nu are niciun prieten la dreapta sa, şirul rămânând vid);

 • pentru fiecare $k ≥ 2$, $d$~$k$~ este cel mai mic indice $(1 ≤ d$~$k$~ $≤ n)$ cu proprietatea că $d$~$k$~ > $d$~$k-1$~ şi $H$~$dk$~ > $H$~$dk-1$~. Dacă $d$~$k$~ nu există, atunci lista de prieteni la dreapta ai copacului $i$ s-a încheiat şi construirea şirului se opreşte la acest pas.
 

 • pentru fiecare $k ≥ 2$, $d$~$k$~ este cel mai mic indice $(1 ≤ d$~$k$~ $≤ n)$ cu proprietatea că $d$~$k$~ > $d$~$k-1$~ şi $H$~d{$~k~$}~ > $H$~d{$~k-1~$}~ . Dacă $d$~$k$~ nu există, atunci lista de prieteni la dreapta ai copacului $i$ s-a încheiat şi construirea şirului se opreşte la acest pas.

# • $s$~$1$~ $= i - 1$ (daca $i = 1$, atunci copacul $i$ nu are niciun prieten la stânga sa, sirul rămânând vid);

 • pentru fiecare $k &ge; 2$, $s$~$k$~ este cel mai mare indice $(1 &le; s$~$k$~ $&le; n)$ cu proprietatea că $s$~$k$~ < $s$~$k-1$~ şi $H$~$sk$~ > $H$ ~$sk-1$~. Dacă $s$~$k$~ nu există, atunci lista de prieteni la stânga ai copacului $i$ s-a încheiat şi construirea şirului se opreşte la acest pas.

 • pentru fiecare $k &ge; 2$, $s$~$k$~ este cel mai mare indice $(1 &le; s$~$k$~ $&le; n)$ cu proprietatea că $s$~$k$~ < $s$~$k-1$~ şi $H$~s{$~k~$}~ > $H$~s{$~k-1~$}~ . Dacă $s$~$k$~ nu există, atunci lista de prieteni la stânga ai copacului $i$ s-a încheiat şi construirea şirului se opreşte la acest pas.
 
p<>. De exemplu, în figura de mai jos sunt reprezentaţi $7$ copaci, fiecare având precizată sub el valoarea înălţimii sale. Primul copac din stânga are indicele $1$, iar ultimul are indicele $7$.
 
{!>problema/copaci4?x.jpg!}
 
p<>. Copacul $1$ este prieten cu copacul $2$ fiind vecini, cu copacul $5$ (deoarece copacul $5$ este primul din dreapta lui $2$ cu înălţimea mai mare strict decât înălţimea lui $2$). La dreapta copacului $5$ nu exista niciun copac cu înălţimea mai mare strict decât a sa, deci singurii prieteni ai copacului $1$ sunt $2$ şi $5$.
 
p<>. Pentru copacul $3$, prietenii la stânga sa sunt copacii $2$ şi $1$, iar cei de la dreapta sa sunt copacii $4$ şi $5$. Pentru copacul $6$, singurul prieten la stânga este copacul $5$, iar la dreapta copacul $7$.
 
p<>. Copacul $7$ poate avea prieteni doar la stânga, aceştia sunt $6$ şi $5$ (la stânga copacului $5$ nu mai există niciun copac cu înălţimea mai mare strict decât $8$).
 
p<>. Grădinarul Marian vrea să aleagă $3$ copaci diferiţi dintre cei $n$ pentru a-i planta în altă grădină. El doreşte ca dintre cei $3$ copaci, oricum ar alege $A$ si $B$, $2$ dintre ei, atunci $A$ este prieten cu $B$ şi $B$ este prieten cu $A$ (relaţiile de prietenie se consideră cele stabilite iniţial). Marian are mai multe opţiuni şi se întreabă în câte moduri distincte poate alege cei $3$ copaci cu proprietatea cerută.
 
h2. Cerinţă
 
p<>. Determinaţi în câte moduri se pot alege $3$ copaci diferiţi dintre cei $n$ cu proprietatea că, oricum am alege $2$ copaci dintre cei $3$, fie aceştia copacul $A$ şi copacul $B$, atunci $A$ este prieten cu $B$ şi $B$ este prieten cu $A$.

h2. Date de intrare

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

p<>. Fişierul de intrare $copaci4.in$ conţine pe prima linie un număr natural $n$, reprezentând numărul de copaci, iar pe a doua linie $n$ numere naturale nenule, separate prin câte un spaţiu, reprezentând înălţimile copacilor.

h2. Date de ieşire

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

p<>. Fişierul de ieşire $copaci4.out$ va conţine pe prima linie un număr natural reprezentând numărul de moduri în care Marian poate alege $3$ copaci cu proprietatea din enunţ.

h2. Restricţii

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

* $1 ≤ n ≤ 200 000$;
* $1 ≤ H$~$i$~ $≤ 200$;
* nu vor exista $2$ copaci alăturaţi cu aceeaşi înălţime;
* două triplete de copaci se consideră distincte dacă există cel puţin un copac din primul triplet care nu se află şi în al doilea triplet;
* pentru $30%$ din teste, $1 ≤ n ≤ 200$.

h2. Exemplu
 
table(example). |_. copaci4.in |_. copaci4.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
h3. Explicaţie

h2. Exemplu

...

table(example). |_. copaci4.in |_. copaci4.out |_. Explicaţie |
| 7
6 4 2 3 8 5 8
| 4
| Copacul 1 este prieten cu copacii: 2, 5
Copacul 2 este prieten cu copacii: 1, 3, 4, 5
Copacul 3 este prieten cu copacii: 1, 2, 4, 5
Copacul 4 este prieten cu copacii: 1, 2, 3, 5
Copacul 5 este prieten cu copacii: 1, 2, 4, 6, 7
Copacul 6 este prieten cu copacii: 5, 7
Copacul 7 este prieten cu copacii: 5, 6
Modurile in care Marian poate alege cei 3 copaci sunt:
(1, 2, 5), (2, 4, 5), (2, 3, 4), (5, 6, 7).
|

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

7731