description: Petya has an array of integers a_1, a_2, …, a_n. He only likes sorted arrays. Unfortunately, the given array could be arbitrary, so Petya wants to sort it.
  
  Petya likes to challenge himself, so he wants to sort array using only 3-cycles. More formally, in one operation he can pick 3 pairwise distinct indices i, j, and k (1 ≤ i, j, k ≤ n) and apply i → j → k → i cycle to the array a. It simultaneously places a_i on position j, a_j on position k, and a_k on position i, without changing any other element.
  
  For example, if a is [10, 50, 20, 30, 40, 60] and he chooses i = 2, j = 1, k = 5, then the array becomes [\underline{50}, \underline{40}, 20, 30, \underline{10}, 60].
  
  Petya can apply arbitrary number of 3-cycles (possibly, zero). You are to determine if Petya can sort his array a, i. e. make it non-decreasing.
  
  Input
  
  Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 5 ⋅ 10^5). Description of the test cases follows.
  
  The first line of each test case contains a single integer n (1 ≤ n ≤ 5 ⋅ 10^5) — the length of the array a.
  
  The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n).
  
  It is guaranteed that the sum of n over all test cases does not exceed 5 ⋅ 10^5.
  
  Output
  
  For each test case, print "YES" (without quotes) if Petya can sort the array a using 3-cycles, and "NO" (without quotes) otherwise. You can print each letter in any case (upper or lower).
  
  Example
  
  Input
  
  
  7
  1
  1
  2
  2 2
  2
  2 1
  3
  1 2 3
  3
  2 1 3
  3
  3 1 2
  4
  2 1 4 3
  
  
  Output
  
  
  YES
  YES
  NO
  YES
  NO
  YES
  YES
  
  Note
  
  In the 6-th test case Petya can use the 3-cycle 1 → 3 → 2 → 1 to sort the array.
  
  In the 7-th test case Petya can apply 1 → 3 → 2 → 1 and make a = [1, 4, 2, 3]. Then he can apply 2 → 4 → 3 → 2 and finally sort the array.
solution: # Problem: D. Ещё одна задача на сортировку
  # Contest: Codeforces - Codeforces Round #759 (Div. 2, основан на Отборочном раунде 3 Технокубка 2022)
  # URL: https://codeforces.com/contest/1591/problem/D
  # Memory Limit: 256 MB
  # Time Limit: 2000 ms
  # 
  # Powered by CP Editor (https://cpeditor.org)
  
  import bisect
  
  mod = 10 ** 9 + 7
  eps = 10 ** -9
  
  
  def __gcd(a, b):
  	return a if b == 0 else __gcd(b, a % b)
  	
  
  def __lcm(a, b):
  	return a * b / __gcd(a, b)
  
  
  def __fact(n):
  	return 1 if n == 1 else n * __fact(n - 1)
  
  
  def __mex(a):
  	mex = 0
  	a.sort()
  	for x in a:
  		if x <= mex:
  			mex += 1
  		else:
  			break
  	return mex
  
  def __dist(x1, y1, x2, y2):
  	return (x1 - x2) ** 2 + (y1 - y2) ** 2
  
  def __getprimes(n):
      isprime = [True for i in range(n + 1)]
      primes = []
       
      for i in range(2, n + 1):
          if isprime[i]:
              for j in range(i * i, n + 1, i):
                  isprime[j] = False
      for i in range(2, n + 1):
          if isprime[i]:
              primes.append(i)
      return primes
  
  def __modInverse(a, m):
      
      m0 = m
      y = 0
      x = 1
      if (m == 1):
          return 0
      
      while(a > 1):
      	q = a // m
      	t = m
      	m = a % m
      	a = t
      	t = y
      	y = x - q * y
      	x = t
      if (x < 0):
      	x = x + m0
      return x
      
      
      
  def __isprime(n):
  	if n < 2:
  		return False
  	i = 2
  	while i * i <= n:
  		if n % i == 0:
  			return False
  		i += 1
  	return True
  	
  def __cntprimediv(n):
  	ret = 0
  	x = n
  	i = 2
  	while i * i <= x:
  		while n % i == 0:
  			n //= i
  			ret += 1
  		i += 1
  	if n > 1:
  		ret += 1
  	return ret
  	
  def __primefactors(n):
  	ret = []
  	x = n
  	i = 2
  	while i * i <= x:
  		while n % i == 0:
  			ret.append(i)
  			n //= i
  		i += 1
  	if n > 1:
  		ret.append(n)
  	return ret
  	
  
  def __sumdigit(n):
  	ret = 0
  	while n > 0:
  		ret += n % 10
  		n //= 10
  	return ret
  
  def __zfunc(s):
  	n = len(s)
  	z = [0 for i in range(n)]
  	l = 0
  	r = 0
  	for i in range(1, n):
  		if r >= i:
  			z[i] = min(z[i - l], r - i + 1)
  		while z[i] + i < n and s[z[i]] == s[z[i] + i]:
  			z[i] += 1
  		if i + z[i] - 1 > r:
  			l = i
  			r = i + z[i] - 1
  	return z
  	
  	
  def __to(n, x):
  	ret = ''
  	while n > 0:
  		q = n % x
  		if q < 10:
  			ret += str(q)
  		else:
  			ret += chr(q - 10 + ord('a'))
  		n //= x
  	return ret[::-1]
  	
  	
  def solve(t):
  	n = int(input())
  	a = list(map(int, input().split()))
  	b = sorted(a)
  	mp = {}
  	ok = True
  	for i in range(n):
  		if a[i] in mp:
  			mp[a[i]].append(i)
  			if len(mp[a[i]]) > 1:
  				print('YES')
  				return 
  		else:
  			mp[a[i]] = [i]
  	
  	for pos in range(n):
  		if a[pos] != b[pos]:
  			if len(mp[b[pos]]) > 0:
  				i = pos
  				j = mp[b[pos]][0]
  				k = n - 1
  				if j == k:
  					k -= 1
  					if k <= i:
  						ok = False
  						break
  				mp[a[i]].pop(0)
  				mp[a[j]].pop(0)
  				mp[a[k]].pop(0)
  				
  				a[i], a[j], a[k] = a[j], a[k], a[i]
  				mp[a[j]].append(j)
  				mp[a[k]].append(k)
  			else:
  				ok = False
  				break
  
  	if ok:
  		if a != b:
  			ok = False
  	print('YES' if ok else 'NO')
  	
  t = 1
  t = int(input())
  
  
  for i in range(t):
  	solve(i + 1)