S2c

Fie un șir format din $N$ numere naturale nenule: $a[{1}]$, $a[{2}]$, …, $a[{N}]$. Se numește subșir 2-crescător de lungime k al șirului dat orice subșir $a[{x_1}]$, $a[{x_2}]$, …, $a[{x_k}]$, unde $1 \leq x_1 < x_2 < … < x_k \leq N$ , în care este îndeplinită următoarea proprietate:

• $a[{x_i}]$ < $a[{x_{i+2}}]$, pentru orice $i$, $1 \leq i \leq k – 2$, adică $a[{x_1}]$ < $a[{x_3}]$ < $a[{x_5}]$ < … și $a[{x_2}]$ < $a[{x_4}]$ < $a[{x_6}]$ < …

Cerință

Date fiind $T$ șiruri conform enunțului, se cere să se determine lungimea maximă a câte unui subșir 2-crescător pentru fiecare dintre cele $T$ șiruri date.

Date de intrare

În fișierul de intrare s2c.in se află pe prima linie numărul $T$, reprezentând numărul de șiruri, iar pe fiecare dintre următoarele $2*T$ linii se află descrierile șirurilor. Pe linia $2*i$, se va afla un singur număr natural reprezentând numărul de elemente $N_i$ al celui de-al $i$-lea șir de numere dat. Pe linia $2*i+1$ se vor afla $N_i$ numere naturale, reprezentând numerele din șir, separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire s2c.out se va scrie pe fiecare dintre $T$ linii, fiecare conținând un singur număr natural. Pe linia $i$ se va scrie un număr natural reprezentând lungimea maximă a unui subșir 2-crescător al celui de-al $i$-lea șir din cadrul celor $T$ șiruri date.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq N_i \leq 2000$, pentru fiecare $i$, $ 1 \leq i \leq T$.
• Pentru 30% din punctaj $1 \leq N_i \leq 400$, pentru fiecare $i$, $1 \leq i \leq T$.
• Pentru 60% din punctaj $1 \leq N_i \leq 1000$, pentru fiecare $i$, $1 \leq i \leq T$.
• Elementele din fiecare șir sunt numere naturale nenule din mulțimea ${{1, 2, 3, …, 30000}}$.

Exemplu

s2c.in

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

s2c.out

6
3

Explicații

Avem $T = 2$ teste.

Primul șir are lungimea egală cu $8$. Subșirurile 2-crescătoare de lungime maximă, egală cu $6$, sunt:

• $1, 1, 3, 2, 5, 3$
• $1, 1, 3, 2, 5, 4$
• $1, 1, 3, 2, 5, 5$
• $1, 1, 3, 2, 4, 5$
• $1, 1, 2, 3, 4, 5$

Al doilea șir are lungimea $5$. Subșirurile 2-crescătoare de lungime maximă, egală cu $3$, sunt:

• $6, 4, 7$
• $6, 2, 7$
• $4, 2, 7$