== include(page="template/taskheader" task_id="magicsequence") ==
Poveste şi cerinţă...
În ultimul timp, pe planeta Miada sunt la modă aşa numitele secvenţe magice. Spunem că o secvenţă $V$ este magică dacă poate fi construită din operaţii de tipul:
* Adaugă elementul $X$ în secvenţă. Această operaţie este permisă doar dacă secvenţa este nulă.
* Adaugă elementul $X$ în secvenţă, peste elementul de pe poziţia $pos$:
1. Dacă $V[pos]$ este mai mic decât $X$, atunci toate elementele din secvenţa $V$ începând cu poziţia $pos + 1$ se vor muta cu o poziţie în dreapta, iar $X$ se va plasa pe poziţia $pos + 1$.
2. Dacă $V[pos]$ este mai mare decât $X$, atunci toate elementele din secvenţa $V$, începând cu poziţia $pos$ se vor muta cu o poziţie în dreapta, iar $X$ se va plasa pe poziţia $pos$.
Se dau $T$ secvenţe. Să se spună pentru fiecare secvenţă în parte dacă este sau nu o secvenţă magică.
h2. Date de intrare
Fişierul de intrare $magicsequence.in$ ...
Fişierul de intrare $magicsequence.in$ conţine pe prima linie $T$, reprezentând numărul de teste. În continuare, pentru fiecare test, se va găsi pe prima linie un număr natural $N$, reprezentând lungimea secvenţei, iar pe cea de-a doua linie $N$ numere naturale *distincte*, reprezentând numerele din secvenţă.
h2. Date de ieşire
În fişierul de ieşire $magicsequence.out$ ...
În fişierul de ieşire $magicsequence.out$ se vor găsi $T$ linii, pe linia $i$ găsindu-se răspunsul pentru testul $i$: *YES* dacă secvenţa este magică, respectiv *NO* dacă nu este.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 20.000$
* $1 ≤ V[i] ≤ 10^9^. Numerele sunt distincte două câte două.$
h2. Exemplu
table(example). |_. magicsequence.in |_. magicsequence.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
3
2 1 3
2
2 1
| YES
NO
|
h3. Explicaţie
...
Pentru primul exemplu, putem obţine secvenţa astfel:
1. Adăugăm $2$ în secvenţă.
2. Adăugăm $3$ în secvenţă, peste $2$. Secvenţa devine $2 3$.
3. Adăugam $1$ în secvenţă, peste $3$. Secvenţa devine $2 1 3$.
== include(page="template/taskfooter" task_id="magicsequence") ==
