| Fişierul intrare/ieşire: | magicsequence.in, magicsequence.out | Sursă | Algoritmiada 2015 Runda 1 |
| Autor | Teodor Plop | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Magic Sequence
Î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ă.
Date de intrare
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ţă.
Date de ieşire
Î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.
Restricţii
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 20.000
- 1 ≤ V[i] ≤ 109. Numerele sunt distincte două câte două.
Exemplu
| magicsequence.in | magicsequence.out |
|---|---|
| 2 3 2 1 3 2 2 1 | YES NO |
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.
