| Fişierul intrare/ieşire: | compact2.in, compact2.out | Sursă | Algoritmiada 2015 Runda Finala |
| Autor | Mihai Calancea | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Compact2
Fie A un şir de N numere naturale distincte. Spunem că A este compact dacă există un interval [a, b] de lungime N astfel încât toate numerele din A se află în acest interval. Spunem că A este supercompact dacă orice prefix al său este compact. Spre exemplu şirul [2, 4, 3, 5] este compact, dar nu este supercompact. Şirul [4, 3, 2, 5] este supercompact.
Dându-se o permutare P se cere lungimea celui mai lung subşir supercompact al ei. Reamintim ca un subsir al unui sir de numere se obtine prin stergerea unor elemente din sirul initial (posibil niciunul). Astfel, [3, 5, 1] este subsir al sirului [3, 2, 4, 5, 6, 1], dar [3, 4] nu este subsir al sirului [4 5 3].
Date de intrare
Fişierul de intrare compact2.in va conţine pe prima sa linie numărul N, reprezentând dimensiunea lui P. Cea de a doua linie va conţine N numere naturale care formează o permutare.
Date de ieşire
În fişierul de ieşire compact2.out se va afla exact un număr natural, lungimea celui mai lung subşir supercompact al permutării P.
Restricţii
- 1 ≤ N ≤ 1.000.000
- Pentru 10% din punctaj N ≤ 20
- Pentru 30% din punctaj N ≤ 1000
Exemplu
| compact2.in | compact2.out |
|---|---|
| 5 4 2 5 1 3 | 3 |
