CSES - Datatähti 2021 loppu - Järjestäminen
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Annettuna on lista, jossa on luvut $1,2,\dots,n$ jossain järjestyksessä.

Tehtäväsi on tutkia, voiko luvut järjestää pienimmästä suurimpaan toistamalla seuraavaa operaatiota mikä tahansa määrä kertoja: valitaan kaksi erillistä vierekkäisten lukujen paria ja vaihdetaan nämä parit keskenään.

Esimerkiksi lista $[2,3,5,1,4]$ voidaan järjestää kahdella operaatiolla: $[\underline{2,3},5,\underline{1,4}] \rightarrow [1,\underline{4,5},\underline{2,3}] \rightarrow [1,2,3,4,5]$.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $t$: testien määrä.

Jokaisen testin ensimmäisellä rivillä on kokonaisluku $n$ ja toisella rivillä listan sisältö.

Tuloste

Tulosta jokaisesta testistä YES, jos listan voi järjestää, ja muuten NO.

Esimerkki

Syöte:
3
2
1 2
5
2 3 5 1 4
4
1 2 4 3


Tuloste:
YES
YES
NO


Osatehtävä 1 (36 pistettä)
  • $1 \le t \le 1000$
  • $1 \le n \le 8$
Osatehtävä 2 (64 pistettä)
  • $1 \le t \le 1000$
  • $1 \le n \le 100$