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

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

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$ conţine pe prima linie numărul întreg N. Pe urmatoarele N linii, se află câte un număr intreg din permutarea dată.

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

* $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
table(example). |_. intervale.in |_. intervale.out |
| 6
1 2 6 4 5 3

| 14

| 13

|
h3. Explicaţie

Cele 14 intervale compacte din exemplu sunt:

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
* 5 3
* 3

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