Chef is working on his swap-based sorting algorithm for strings.

Given a string S of length N, he wants to know whether he can sort the string using his algorithm.

According to the algorithm, one can perform the following operation on string S any number of times:
Choose some index i (1 ≤ i ≤ N) and swap the i^{th} character from the front and the i^{th} character from the back.  
More formally, choose an index i and swap S_{i} and S_{(N+1-i)}.

For example, \underline{\texttt{d}} \texttt{cb} \underline{\texttt{a}} can be converted to \underline{\texttt{a}} \texttt{cb} \underline{\texttt{d}} using one operation where i = 1.

Help Chef find if it is possible to sort the string using any (possibly zero) number of operations.

------ Input Format ------ 

- The first line of the input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains N, the length of the string.
- The second line contains a string S of length N consisting of lowercase letters of the Latin alphabet.

------ Output Format ------ 

For each test case, print \texttt{YES} if it is possible to sort the string by performing any number of operations. Otherwise, print \texttt{NO}.

You may print each character of the string in uppercase or lowercase (for example, the strings \texttt{YeS}, \texttt{yEs}, \texttt{yes} and \texttt{YES} will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{3}$
- Sum of $N$ over all test cases does not exceed $2\cdot10^{3}$.
$S$ consists of lowercase Latin alphabets only.

----- Sample Input 1 ------ 
3
4
dbca
3
ccc
3
bza
----- Sample Output 1 ------ 
YES
YES
NO
----- explanation 1 ------ 
Test case $1$: Chef can sort the string using $1$ operation.
- Choose $i = 1$ and swap $S_{1} = \texttt{d}$ and $S_{4} = \texttt{a}$.
This way, the string becomes $\texttt{abcd}$.

Hence, the string is sorted.

Test case $2$: Chef needs $0$ operations to sort this string as it is already sorted.

Test case $3$: It can be proven that the given string cannot be sorted using any number of operations.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	s = input()
	l = list(s)
	f = sorted(l)
	if l == f:
		print('YES')
	else:
		c = 0
		for i in range(n):
			if l[i] > l[n - 1 - i]:
				(l[i], l[n - 1 - i]) = (l[n - 1 - i], l[i])
			if l == f:
				c += 1
				break
		if c == 1:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(input())
	p = sorted(l)
	if p == l:
		print('YES')
	else:
		for i in range(n // 2):
			if l[i] > l[n - 1 - i]:
				(l[i], l[n - i - 1]) = (l[n - 1 - i], l[i])
		print('YES') if p == l else print('NO')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	s1 = sorted(s)
	if s == s1:
		print('YES')
	else:
		for i in range(n // 2):
			if s[i] > s[n - 1 - i]:
				(s[i], s[n - 1 - i]) = (s[n - 1 - i], s[i])
		if s == s1:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	i = 0
	while i < n:
		if ord(s[i]) > ord(s[n - 1]):
			(s[i], s[n - 1]) = (s[n - 1], s[i])
		i += 1
		n -= 1
	c = 0
	for i in range(len(s) - 1):
		if ord(s[i]) > ord(s[i + 1]):
			c = 1
			break
	if c == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	j = int(input())
	l = list(input())
	i = 0
	while i < j:
		if ord(l[i]) > ord(l[j - 1]):
			n = l[j - 1]
			l[j - 1] = l[i]
			l[i] = n
		i = i + 1
		j = j - 1
	c = 0
	for i in range(1, len(l)):
		if ord(l[i - 1]) > ord(l[i]):
			c = 1
			break
	if c == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	i = 0
	j = n - 1
	front = '0'
	rear = 'Z'
	found = False
	while i <= j:
		if s[i] > s[j]:
			temp = s[i]
			s[i] = s[j]
			s[j] = temp
		if i == 0:
			front = s[i]
			rear = s[j]
		elif s[i] >= front and s[j] <= rear:
			front = s[i]
			rear = s[j]
		else:
			found = True
			break
		i += 1
		j -= 1
	if not found:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	i = 0
	j = n - 1
	while i < j:
		if s[i] > s[j]:
			temp = s[i]
			s[i] = s[j]
			s[j] = temp
		i += 1
		j -= 1
	if sorted(s) == s:
		print('YES')
	else:
		print('NO')


t = int(input())
for I in range(t):
	n = int(input())
	l = list(input())
	k = sorted(l)
	for i in range(n):
		if l[i] != k[i] and l[i] != k[n - i - 1]:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	for j in range(n // 2):
		if alpha.index(s[j]) > alpha.index(s[-(j + 1)]):
			(s[j], s[-(j + 1)]) = (s[-(j + 1)], s[j])
	for x in range(n - 1):
		if alpha.index(s[x]) > alpha.index(s[x + 1]):
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for i in range(0, t):
	n = int(input())
	li = list(input())
	p = sorted(li)
	a = n // 2
	if p == a:
		print('YES')
	else:
		for i in range(a):
			if li[i] > li[n - 1 - i]:
				(li[i], li[n - i - 1]) = (li[n - 1 - i], li[i])
		print('YES') if p == li else print('NO')


def swap(n, s):
	if s == sorted(s):
		return 'YES'
	else:
		for i in range(n):
			if ord(s[i]) < ord(s[n - i - 1]):
				(s[i], s[n - i - 1]) = (s[n - i - 1], s[i])
	if s == sorted(s):
		return 'YES'
	else:
		return 'NO'
for _ in range(int(input())):
	n = int(input())
	s = [i for i in input()]
	print(swap(n, s))


n = int(input())
for i in range(n):
	a = int(input())
	s = input()
	(l, k) = ([], [])
	l.extend(s)
	k.extend(s)
	k.sort()
	for i in range(len(s) // 2):
		if l[i] >= l[-(i + 1)]:
			te = l[-(i + 1)]
			l[-(i + 1)] = l[i]
			l[i] = te
	if k == l:
		print('YES')
	else:
		print('NO')


t = int(input())
for tc in range(t):
	n = int(input())
	l = list(input())
	d = sorted(l)
	if d == l:
		print('YES')
	else:
		for j in range(n // 2):
			if l[j] > l[n - 1 - j]:
				(l[j], l[n - 1 - j]) = (l[n - 1 - j], l[j])
		if d == l:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = list(map(str, s))
	l1 = l.copy()
	l.sort()
	x = ''.join(l)
	count = 0
	for i in range(len(s) // 2):
		if l1[i] > l1[len(s) - 1 - i]:
			(l1[i], l1[len(s) - 1 - i]) = (l1[len(s) - 1 - i], l1[i])
			count += 1
	y = ''.join(l1)
	if x == y and count <= n:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	l = int(input())
	st = input()
	ls = [x for x in st]
	ls.sort()
	c = 1
	for i in range(len(ls)):
		if st[i] == ls[i]:
			pass
		elif st[i] == ls[len(ls) - 1 - i]:
			pass
		else:
			c = 0
			break
	print('YES' if c != 0 else 'NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	string = sorted(s)
	c = 0
	if string == s:
		print('YES')
	else:
		for j in range(n // 2):
			if s[j] > s[n - j - 1]:
				(s[j], s[n - j - 1]) = (s[n - j - 1], s[j])
				if s == string:
					c = 1
					break
		if c == 1:
			print('YES')
		else:
			print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	S = list(input().lower())
	P = sorted(S)
	if P == S:
		print('YES')
	else:
		j = 0
		while j < len(S) // 2:
			if S[j] > S[len(S) - 1 - j]:
				(S[j], S[len(S) - 1 - j]) = (S[len(S) - 1 - j], S[j])
			j += 1
		if S == P:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	for i in range(n // 2):
		if s[i] > s[n - i - 1]:
			(s[i], s[n - i - 1]) = (s[n - i - 1], s[i])
	sorts = True
	for i in range(n - 1):
		if s[i] > s[i + 1]:
			sorts = False
	if sorts:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	m = sorted(s)
	s = list(s)
	mid = n // 2
	for i in range(mid):
		if s[i] > s[n - 1 - i]:
			(s[i], s[n - 1 - i]) = (s[n - 1 - i], s[i])
	if m == s:
		print('YES')
	else:
		print('NO')


def solve():
	n = int(input())
	s = input()
	p = list(s)
	i = 0
	j = len(s) - 1
	while i < j:
		if p[i] > p[j]:
			(p[i], p[j]) = (p[j], p[i])
		j += -1
		i += 1
	s = ''.join(p)
	print('YES' if s == ''.join(sorted(s)) else 'NO')
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	a = int(input())
	b = input()
	b = list(b)
	c = sorted(b)
	for i in range(a // 2):
		if b[i] > b[-i - 1]:
			(b[i], b[-i - 1]) = (b[-i - 1], b[i])
	if b == c:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	s1 = s
	s1 = ''.join(sorted(s1))
	start = 0
	end = len(s) - 1
	l = [*s]
	while start < end:
		if l[start] > l[end]:
			(l[start], l[end]) = (l[end], l[start])
		start += 1
		end -= 1
	newstr = ''.join(l)
	if newstr == s1:
		print('YES')
	else:
		print('NO')


s = int(input())
gt = []
for mm in range(0, s):
	hy = int(input())
	kl = str(input())
	gt.append(kl)
for ii in gt:
	um = list(ii)
	um.sort()
	op = ''.join(um)
	if op == ii:
		print('YES')
	else:
		ime = list(ii)
		opcxz = 0
		for kkt in range(0, len(ime)):
			imt = ime[kkt]
			num = len(ime) - kkt - 1
			if kkt == num:
				ime[kkt] = imt
				break
			else:
				umtpo = ime[num]
				if ord(umtpo) <= ord(imt):
					ime[kkt] = umtpo
					ime[num] = imt
			frt = ''.join(ime)
			if frt == op:
				opcxz = 1
				print('YES')
				break
		if opcxz == 0:
			hytv = ''.join(ime)
			if hytv == op:
				print('YES')
			else:
				print('NO')


for _ in range(int(input())):
	x = int(input())
	s = input()
	l = list(s)
	p = sorted(s)
	k = list(p)
	for i in range(x):
		if l[i] <= l[x - i - 1]:
			(l[i], l[x - i - 1]) = (l[x - i - 1], l[i])
		else:
			pass
	if k == l:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = [*input()]
	string = [*''.join(sorted(s))]
	for i in range(n // 2):
		temp = 0
		if s[i] > s[n - i - 1]:
			temp = s[i]
			s[i] = s[n - i - 1]
			s[n - i - 1] = temp
	if s == string:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	i = 0
	j = len(s) - 1
	s1 = sorted(s)
	f = 0
	if s1 == s:
		print('YES')
	else:
		while i <= j:
			if s[i] > s[j]:
				(s[i], s[j]) = (s[j], s[i])
			i += 1
			j -= 1
		if s == s1:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	s1 = sorted(s)
	j = 0
	k = len(s) - 1
	if s1 == s:
		print('YES')
	else:
		while j <= k:
			if s[j] > s[k]:
				(s[j], s[k]) = (s[k], s[j])
			j = j + 1
			k = k - 1
		if s == s1:
			print('YES')
		else:
			print('NO')


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	i = 0
	j = len(s) - 1
	s1 = sorted(s)
	f = 0
	if s1 == s:
		print('YES')
	else:
		while i <= j:
			if s[i] > s[j]:
				(s[i], s[j]) = (s[j], s[i])
			i += 1
			j -= 1
		if s == s1:
			print('YES')
		else:
			print('NO')


T = int(input())
for i in range(T):
	n = int(input())
	s = [i for i in input()]
	l = list(s)
	l.sort()
	if l == s:
		print('YES')
	else:
		f = 0
		for i in range(n // 2):
			if s[i] > s[-(i + 1)]:
				(s[i], s[-(i + 1)]) = (s[-(i + 1)], s[i])
			if s == l:
				print('YES')
				break
		else:
			print('NO')


T = int(input())
for t in range(T):
	N = int(input())
	S = list(input())
	sorted_string = sorted(S)
	for i in range(len(S) - 1):
		if S[i] != sorted_string[i]:
			temp = S[i]
			S[i] = S[N - 1 - i]
			S[N - 1 - i] = temp
	if S == sorted_string:
		print('YES')
	else:
		print('NO')


import math
for t_c in range(int(input())):
	n = int(input())
	s = input()
	s = [i for i in s]
	for i in range(n // 2):
		if s[i] > s[-(i + 1)]:
			(s[i], s[-(i + 1)]) = (s[-(i + 1)], s[i])
	for i in range(1, n):
		if s[i - 1] > s[i]:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	lst_a = list(input())
	sort_a = sorted(lst_a)
	for i in range(len(lst_a) - 1):
		if lst_a[i] != sort_a[i]:
			x = lst_a[i]
			lst_a[i] = lst_a[n - i - 1]
			lst_a[n - i - 1] = x
	if lst_a == sort_a:
		print('YES')
	else:
		print('NO')


for pc in range(int(input())):
	n = int(input())
	s = list(input())
	a = sorted(s)
	for i in range(len(s) - 1):
		if s[i] != a[i]:
			x = s[i]
			s[i] = s[n - 1 - i]
			s[n - 1 - i] = x
	if s == a:
		print('YES')
	else:
		print('NO')