== include(page="template/taskheader" task_id="scmax2") ==

Poveste şi cerinţă...

Se da un sir de numere. Sa se gaseasca cel mai lung subsir crescator. Formal, sa se elimine un numar cat mai mic de numere in asa fel incat numerele ramase sa formeze un sir strict crescator, si sa se afiseze numarul de numere ramase.
 
Glumim. *Cui* i-ar trebui asa ceva in viata reala?
 
Pe noi ne intereseaza ceva mult mai profund.
 
h2. Cerinta
 
Fiecare numar $a$ are un numar preferat $T{~a~}$, care desi (dupa regulile obisnuite e garantat ca) $T{~a~} &le; a$, numarul $a$ e gata sa considere ca $a < T{~a~}$, daca asta l-ar aduce pe $T{~a~}$ imediat in dreapta lui $a$ in subsirul crescator pe care il consideram. Adica, pe langa regulile obisnuite care spun cand e un numar mai mic decat altul, introducem relatiile $a < T{~a~}$ (fara sa stergem relatia $T{~a~} < a$).
 
Sa se gaseasca subsirul crescator maximal, vand in vedere noile conditii.
 
Formal, un sir este (mai nou) strict crescator daca pentru fiecare pereche de numere consecutive din sir $(left, right)$, fie $left < right$ fie $T{~left~} = right$.

h2. Date de intrare

Fişierul de intrare $scmax2.in$ ...

Fişierul de intrare $scmax2.in$ contine pe prima linie numarul $T$ de teste din fisier. Pentru fiecare test descrierea e asemanatoare: Pe prima linie numarul natural $N$ de numere din sir. Pe urmatoarea linie se afla $N$ numere naturale cu valori intre $1$ si $N$, reprezentand sirul. Pe urmatoarea linie se afla $N$ numere naturale cu valori intre $1$ si $N$, al $i$-ulea dintre acestea find $T{~i~}$.

h2. Date de ieşire

În fişierul de ieşire $scmax2.out$ ...

În fişierul de ieşire $scmax2.out$ se afla marimea celui mai lung subsir crescator maximal al sirului, avand in vedere noi reguli.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 50.000$
* Pentru $10$ puncte, $N ≤ 14$
* Pentru alte $10$ puncte, $N ≤ 100$
* Pentru alte $10$ puncte, $T{~i~} = i$ pentru orice $i$
* Pentru alte $10$ puncte, toate numerele din sir sunt fie $1$, fie $2$, fie $3$
* Pentru alte $10$ puncte, pentru fiecare numar $a$ exista cel mult 3 numere $b$ pentru care $T{~b~} = a$

h2. Exemplu