== include(page="template/taskheader" task_id="compact2") ==
Poveste şi cerinţă...
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]$.
h2. Date de intrare
Fişierul de intrare $compact2.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $compact2.out$ ...
Î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$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1.000.000$
* Pentru $10%$ din punctaj $N ≤ 20$
* Pentru $30%$ din punctaj $N ≤ 1000$
h2. Exemplu
table(example). |_. compact2.in |_. compact2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5
4 2 5 1 3
|3
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="compact2") ==
