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$).

Fiecare numar $a$ are un numar preferat $T{~a~}$, care desi poate fi (dupa regulile obisnuite) $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.

Sa se gaseasca subsirul crescator maximal, avand 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$ 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~}$.

Fişierul de intrare $scmax2.in$ contine pe prima linie numarul $Q$ 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

h2. Restricţii

* $1 ≤ Q ≤ 5$

* $1 ≤ N ≤ 50.000$
* Pentru $10$ puncte, $N ≤ 14$
* Pentru alte $10$ puncte, $N ≤ 100$

h2. Exemplu
table(example). |_. scmax2.in |_. scmax2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
 10
 4 1 6 1 8 10 10 1 9 1
 3 6 3 2 1 9 8 1 5 10
 8
 8 1 8 6 4 8 5 7
 7 3 2 8 8 4 5 6
| 5
 6

|
h3. Explicaţie

...

In primul test secventa maximala este 4 6 8 10 10
In al doilea test secventa maximala este  1 8 6 4 5 7

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