Fişierul intrare/ieşire:intervale.in, intervale.outSursăLot Sibiu 2011
AutorCosmin Silvestru Negruseri, Paul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.8 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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

intervale.inintervale.out
6
1 2 6 4 5 3
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content