Sắp xếp bằng chu trình độ dài 3

Cho một mảng gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$ với $1\le a_i\le n$. Bạn muốn sắp xếp mảng theo thứ tự không giảm.

Bạn chỉ được phép dùng một loại thao tác duy nhất, gọi là chu trình độ dài 3 (3-cycle): chọn ba chỉ số phân biệt $i,j,k$ ($1\le i,j,k\le n$) rồi đồng thời chuyển $a_i$ tới vị trí $j$, $a_j$ tới vị trí $k$, và $a_k$ tới vị trí $i$ (các phần tử khác giữ nguyên).

Ví dụ với mảng $[10,50,20,30,40,60]$, chọn $i=2,j=1,k=5$ thì mảng trở thành $[50,40,20,30,10,60]$.

Bạn được dùng số thao tác tùy ý (có thể bằng $0$). Hãy xác định xem có thể sắp xếp mảng $a$ thành không giảm hay không.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ — độ dài mảng.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra "YES" nếu có thể sắp xếp mảng bằng các chu trình độ dài 3, ngược lại in ra "NO". Có thể in chữ hoa hoặc chữ thường tùy ý.

Ràng buộc

• $1\le t\le 5·{10}^5$
• $1\le n\le 5·{10}^5$
• $1\le a_i\le n$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $5·{10}^5$.

Ví dụ