szceas

Presupunem un șir $A$ de $N$ numere întregi, indexate de la 1 la $N$, și două poziții $i$ și $j$, astfel încât 1 ≤ $i$ < $j$ ≤ $N$.
Numim șirul $A$ aproape sortat, dacă atunci când $a_i$ își interschimbă valoarea cu $a_j$, șirul $A$ devine strict crescător.

Cerință

Dându-se numărul N și elementele șirului A, determinați dacă șirul dat este aproape sortat.

Date de intrare

Pe prima linie se găsește numărul $T$, reprezentând numărul de teste.
Pe următoarele $2 * T$ linii sunt dispuse cele $T$ teste, sub forma: prima linie conține un număr natural $N$, iar cea de-a doua linie $N$ numere întregi, elementele șirului $A$. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Se vor afișa $T$ linii, răspunsurile celor $T$ interogări. Fiecare linie dintre acestea va conține un singur cuvânt, $“DA”$ sau $“NU”$, reprezentând răspunsul întrebării “Șirul $A$ este aproape sortat?”.

Restricții și precizări

• $1 \leq$ N $\leq 100 \ 000$;
• $1 \leq$ Suma tuturor numerelor N $\leq 5 \ 000 \ 000$;
• $1 \leq T \leq 100 \ 000$;
• Numerele sunt distincte între ele;
• $1 \leq a_i \leq 1 \ 000 \ 000 \ 000, \ i ∈ {1, 2, ..., n}$.

Observație

Datorită datelor de intrare foarte mari, se vor folosi instrucțiunile următoare la începutul programului:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Exemplu

stdin

2
5
1 7 5 3 9
4
1 2 3 4

stdout

DA
NU

Explicație

Pentru primul test, dacă interschimbăm elementul de pe poziția 2 cu elementul de pe poziția 4, șirul A devine:
$1 \ 3 \ 5 \ 7 \ 9$, care este un șir sortat.
În cel de-al doilea test, șirul este deja sortat. Astfel, el nu este aproape sortat.