Petya has an array of integers $a_1, a_2, \ldots, 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 \leq i, j, k \leq n$) and apply $i \to j \to k \to 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 \leq t \leq 5 \cdot 10^5$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 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).


-----Examples-----

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 \to 3 \to 2 \to 1$ to sort the array.

In the $7$-th test case Petya can apply $1 \to 3 \to 2 \to 1$ and make $a = [1, 4, 2, 3]$. Then he can apply $2 \to 4 \to 3 \to 2$ and finally sort the array.

Difficulty: HARD
Tags: Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
def is_even_perm(a):
	count = 0
	for i in range(len(a)):
		while a[i] != i + 1:
			j = a[i] - 1
			(a[i], a[j]) = (a[j], a[i])
			count += 1
	return count % 2 == 0
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1 or len(a) > len(set(a)):
		print('YES')
		continue
	print('YES' if is_even_perm(a) else 'NO')


def main():
	tests = int(input())
	for _ in range(tests):
		elount = int(input())
		array = [int(x) - 1 for x in input().split()]
		if len(set(array)) != elount:
			print('YES')
			continue
		print('YES' if can_be_trisorted(array) else 'NO')

def can_be_trisorted(arr):
	swaps = 0
	for i in range(len(arr)):
		while arr[i] != i:
			j = arr[i]
			(arr[i], arr[j]) = (arr[j], arr[i])
			swaps = 1 - swaps
	return swaps == 0
main()


for _ in range(int(input())):
	(n, a) = (int(input()), list(map(int, input().split())))
	if len(set(a)) < n:
		print('YES')
		continue
	sorted_a = sorted(a)
	num2i = {num: i for (i, num) in enumerate(sorted_a)}
	vis = [0] * n
	ans = 0
	for i in range(n):
		if vis[i]:
			continue
		(size, cur) = (0, i)
		while not vis[cur]:
			vis[cur] = 1
			(size, cur) = (size + 1, num2i[a[cur]])
		ans += size % 2 == 0
	print('YES') if ans == 0 or ans % 2 == 0 else print('NO')


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	if n == 1:
		print('YES')
	elif n == 2:
		if x[0] <= x[1]:
			print('YES')
		else:
			print('NO')
	else:
		ans = 'NO'
		temp = [0] * n
		for i in range(n):
			temp[x[i] - 1] += 1
			if temp[x[i] - 1] > 1:
				ans = 'YES'
				break
		if ans == 'NO':
			p = 0
			for i in range(n):
				while x[i] != i + 1:
					temp1 = x[i]
					temp2 = x[x[i] - 1]
					x[x[i] - 1] = temp1
					x[i] = temp2
					p += 1
			if p % 2 == 0:
				ans = 'YES'
		print(ans)


from operator import itemgetter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if len(set(arr)) < n:
		print('YES')
	else:
		s = list(map(itemgetter(0), sorted(list(enumerate(arr)), key=itemgetter(1))))
		d = set(range(n))
		ans = 0
		while d:
			z = d.pop()
			while s[z] in d:
				ans += 1
				z = s[z]
				d.remove(z)
		print('YES' if ans % 2 == 0 else 'NO')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) != len(a):
		print('YES')
	elif n == 1:
		print('YES')
	else:
		curridxs = {}
		for (i, x) in enumerate(a):
			curridxs[x] = i
		sorteda = sorted(a)
		for i in range(n - 2):
			if sorteda[i] != a[i]:
				firsti = i
				secondi = curridxs[sorteda[i]]
				thirdi = i + 1 if secondi != i + 1 else n - 1
				firstc = a[firsti]
				secondc = a[secondi]
				thirdc = a[thirdi]
				tempi = firsti
				a[firsti] = secondc
				a[secondi] = thirdc
				a[thirdi] = firstc
				curridxs[firstc] = thirdi
				curridxs[secondc] = firsti
				curridxs[thirdc] = secondi
		if a[n - 2] < a[n - 1]:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('YES')
		continue
	h = n != len(set(a))
	b = sorted(a)
	d = dict()
	for (i, x) in enumerate(a):
		d[x] = d.get(x, set())
		d[x].add(i)
	i = n - 1
	while i > 1:
		r = a[i]
		t = b[i]
		if r != t:
			ti = 0
			for tix in d[t]:
				ti = tix
				break
			z = 0
			if ti == z:
				z = 1
			az = a[z]
			a[i] = t
			d[t].remove(ti)
			a[ti] = a[z]
			d[az].remove(z)
			d[az].add(ti)
			a[z] = r
			d[r].remove(i)
			d[r].add(z)
		i -= 1
	if a[0] == b[0] and a[1] == b[1]:
		print('YES')
	elif h:
		print('YES')
	else:
		print('NO')