intervale

Cerință

Se dă un număr întreg $N$ şi o permutare a mulţimii $(1, 2, \dots, N)$. O subsecvenţă $[i, j]$, $(i \leq 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ă.

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

Date de ieșire

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

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• Pentru $20\%$ din teste, $N \leq 2 \ 000$
• Pentru $60\%$ din teste, $N \leq 35 \ 000$
• Vor fi numărate şi intervalele ce conţin un singur element.

Exemplu

intervale.in

6
1 2 6 4 5 3

intervale.out

13

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$