Fişierul intrare/ieşire:magicsequence.in, magicsequence.outSursăAlgoritmiada 2015 Runda 1
AutorTeodor PlopAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inmagicsequence.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?