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

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