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

Poveste şi cerinţă...

Se dă un număr întreg $N$ şi o permutare a mulţimii ${1, 2, ..., N}$. O subsecvenţă $[i, j]$ $(i ≤ j)$ conţine toate elementele permutării aflate între poziţiile $i$ şi $j$ inclusiv. Se numeşte *interval compact* o subsecvenţă a cărei elemente formează o mulţime de valori consecutive (nu neapărat în ordinea din permutare). De exemplu, pentru permutarea $1 2 6 4 5 3$, subsecvenţele $6 4 5$ si $2 6 4 5 3$ sunt intervale compacte, în timp ce subsecvenţele $1 2 6$ si $2 6 4 5$ nu sunt intervale compacte. Să se determine numărul de intervale compacte din permutarea dată.

h2. Date de intrare

Fişierul de intrare $intervale.in$ contine pe prima linie numarul intreg N. Pe urmatoarele N linii, se afla cate un numar intreg din permutarea data.

Fişierul de intrare $intervale.in$ conţine pe prima linie numărul întreg $N$. Pe urmatoarele $N$ linii, se află câte un număr intreg din permutarea dată.

h2. Date de ieşire

Fişierul de ieşire $intervale.out$ contine un singur numar intreg reprezentand numarul cerut.

Fişierul de ieşire $intervale.out$ conţine un singur număr întreg reprezentând numărul total de intervale compacte din permutarea dată.

h2. Restricţii
* $1 ≤ N ≤ 200 000$
* Pentru $20%$ din teste, $N ≤ 2 000$
* Pentru $60%$ din teste, $N ≤ 35 000$

* Vor fi numărate şi intervalele ce conţin un singur element.

h2. Exemplu

h3. Explicaţie

...

Cele 13 intervale compacte din exemplu sunt:
 
* $1$
* $1 2$
* $1 2 6 4 5 3$
* $2$
* $2 6 4 5 3$
* $6$
* $6 4 5$
* $6 4 5 3$
* $4$
* $4 5$
* $4 5 3$
* $5$
* $3$

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

5640