Revizia anterioară Revizia următoare
| 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.
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 |
