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

Poveste şi cerinţă...

Un şir de numere $a[1], a[2], ..., a[k]$ este bitonic dacă există o poziţie $1 &le i &le n$ astfel încât $a[1] < a[2] < ... < a[i] > a[i+1] > ... > a[k]$ sau $a[1] > a[2] > ... > a[i] < a[i+1] < ... < a[k]$.
 
Dându-se un şir, să se găsească lungimea celui mai lung subşir bitonic.

h2. Date de intrare

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

Fişierul de intrare $bitonic.in$ conţine pe prima linie numărul *T* de teste, iar următoarele linii conţin testele. Fiecare test are două linii: pe prima linie se găseşte numărul *n* de elemente ale şirului şi următoarea linie conţine şirul.

h2. Date de ieşire

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

În fişierul de ieşire $bitonic.out$ se va afişa pentru fiecare test câte o linie conţinând lungimea maximă a unui subşir bitonic al şirului de la intrare.

h2. Restricţii

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

* $ 1 ≤ T ≤ 20 $
* $ 1 ≤ n ≤ 1000 $
* elementele şirului iniţial sunt numere naturale între $0$ şi $100000$

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

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

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

|
h3. Explicaţie

...

Pentru primul exemplu un subşir bitonic de lungime maximă este $1 5 11 3 2$ iar pentru al doilea exemplu $1 2 3 7 6 5 4$.

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