| Fişierul intrare/ieşire: | compact.in, compact.out | Sursă | Algoritmiada 2010, Runda 4 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | compact.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.
