Fişierul intrare/ieşire:compact.in, compact.outSursăAlgoritmiada 2010, Runda 4
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.6 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Compact

Fie P o permutare cu N elemente. Se numeste secventa a permutarii un sir de elemente aflate pe pozitii consecutive. O astfel de secventa de cel putin 3 elemente este compacta daca si numai daca primul element al secventei este minim, in timp ce ultimul element e maxim in raport cu toate elementele secventei. Sa se determine numarul de secvente compacte pentru permutarea P.

Date de intrare

Fisierul de intrare compact.in contine pe prima linie N, numarul de elemente ale permutarii. Cea de a doua linie a fisierului contine N numere naturale distincte, reprezentand elementele permutarii.

Date de iesire

In fisierul de iesire compact.out se va afla un singur numar natural reprezentand numarul secventelor compacte ale permutarii.

Restrictii

  • 3 ≤ N ≤ 1 000 000

Exemplu

compact.incompact.out
8
3 2 7 5 4 8 1 6
1

Explicatie

Singura secventa compacta este (2, 7, 5, 4, 8). Aceasta secventa este compacta deoarece primul element, 2, este minim, iar ultimul, 8, este maxim intre numerele secventei.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content