Fişierul intrare/ieşire:	intervale.in, intervale.out	Sursă	Lot Sibiu 2011
Autor	Cosmin Silvestru Negruseri, Paul-Dan Baltescu	Adăugată de	Paul-Dan Baltescu •pauldb
Timp execuţie pe test	0.4 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 (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

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

Exemplu

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

Cum se trimit solutii?