copaci

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, \ldots, d_x$ reprezentând prietenii copacului $i$ situaţi în dreapta sa şi un şir $s_1, s_2, \ldots, 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_i = i + 1$(dacă $i=n$, atunci copacul $i$ nu are niciun prieten la dreapta sa, şirul $d$ rămânând vid)
• Pentru fiecare $k \geq 2$, $d_k$ este cel mai mic indice ($1 \leq d_k \leq 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 $s$ rămânând vid);
• Pentru fiecare $k \geq 2$, $s_k$ este cel mai mare indice ($1 \leq s_k \leq 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.

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

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

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

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$).

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

Cerință

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

Date de intrare

Fişierul de intrare copaci.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.

Date de ieșire

Fişierul de ieşire copaci.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ţ.

Restricții și precizări

• $1 \leq n \leq 200 \ 000$
• $1 \leq H_i \leq 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 \leq n \leq 200$

Exemplu

copaci.in

7
6 4 2 3 8 5 8

copaci.out

4

Explicație

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)$