Fișierul intrare/ieșire	s2c.in, s2c.out	Sursă	ad-hoc
Autor	Ionel-Vasile Piț-Rada	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.4 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	3.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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₁], a[x₂], ..., a[x_k], unde 1 ≤ x₁ < x₂ < ... < x_k ≤ N, în care este îndeplinită următoarea proprietate:

• a[x_i] < a[x_i+2], pentru orice i, 1 ≤ i ≤ k – 2, adică a[x₁] < a[x₃] < a[x₅] < ... și a[x₂] < a[x₄] < a[x₆] < ...

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 vor scrie 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 ≤ T ≤ 10
• 1 ≤ N_i ≤ 2.000, pentru fiecare i, 1 ≤ i ≤ T.
• Pentru 30% din punctaj 1 ≤ N_i ≤ 400, pentru fiecare i, 1 ≤ i ≤ T.
• Pentru 60% din punctaj 1 ≤ N_i ≤ 1.000, pentru fiecare i, 1 ≤ i ≤ T.
• Elementele din fiecare șir sunt numere naturale nenule din mulțimea {1, 2, 3, ..., 30.000}.

Exemplu

Explicație

...