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ţă ale 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 şi 2 6 4 5 3 sunt intervale compacte, în timp ce subsecvenţele 1 2 6 şi 2 6 4 5 nu sunt intervale compacte.
Cerinţă
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 următoarele N linii, se află câte un număr întreg 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
• 1 ≤ N ≤ 200 000
• Vor fi numărate şi intervalele ce conţin un singur element.
Exemple
intervale.in
intervale.out
Explicaţii
6
1 2 6 4 5 3
13
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