An array $[b_1, b_2, \ldots, b_m]$ is a palindrome, if $b_i = b_{m+1-i}$ for each $i$ from $1$ to $m$. Empty array is also a palindrome.

An array is called kalindrome, if the following condition holds:

It's possible to select some integer $x$ and delete some of the elements of the array equal to $x$, so that the remaining array (after gluing together the remaining parts) is a palindrome.

Note that you don't have to delete all elements equal to $x$, and you don't have to delete at least one element equal to $x$.

For example :

$[1, 2, 1]$ is kalindrome because you can simply not delete a single element.

$[3, 1, 2, 3, 1]$ is kalindrome because you can choose $x = 3$ and delete both elements equal to $3$, obtaining array $[1, 2, 1]$, which is a palindrome.

$[1, 2, 3]$ is not kalindrome.

You are given an array $[a_1, a_2, \ldots, a_n]$. Determine if $a$ is kalindrome or not.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

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

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — elements of the array.

It's guaranteed that the sum of $n$ over all test cases won't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print YES if $a$ is kalindrome and NO otherwise. You can print each letter in any case.


-----Examples-----

Input
4
1
1
2
1 2
3
1 2 3
5
1 4 4 1 4
Output
YES
YES
NO
YES


-----Note-----

In the first test case, array $[1]$ is already a palindrome, so it's a kalindrome as well.

In the second test case, we can choose $x = 2$, delete the second element, and obtain array $[1]$, which is a palindrome.

In the third test case, it's impossible to obtain a palindrome.

In the fourth test case, you can choose $x = 4$ and delete the fifth element, obtaining $[1, 4, 4, 1]$. You also can choose $x = 1$, delete the first and the fourth elements, and obtain $[4, 4, 4]$.

Difficulty: EASY
Tags: Amortized analysis

Greedy algorithms
Skill types: Amortized analysis

Greedy algorithms

Starter code:

Solutions:
for s in [*open(0)][2::2]:
	i = len((a := s.split()))
	while i and a[i - 1] == a[-i]:
		i -= 1
	print('YNEOS'[all((v != v[::-1] for v in ([x for x in a if x != y] for y in (a[i - 1], a[-i]))))::2])


import sys

def kalindrome(S, i, j, canceled_number=0, life=0):
	while True:
		if j - i == 0:
			return True
		elif j - i == 1 and S[i] == S[j]:
			return True
		if S[i] == S[j]:
			i += 1
			j -= 1
		elif S[i] == canceled_number:
			i += 1
		elif S[j] == canceled_number:
			j -= 1
		elif life > 0:
			life -= 1
			return kalindrome(S, i, j, S[i], life - 1) or kalindrome(S, i, j, S[j], life - 1)
		else:
			return False

def solve():
	T = int(sys.stdin.readline().rstrip())
	for _ in range(T):
		N = int(sys.stdin.readline().rstrip())
		S = list(map(int, sys.stdin.readline().rstrip().split(' ')))
		i = 0
		j = N - 1
		print('YES' if kalindrome(S, i, j, 0, 1) else 'NO')
solve()


def solve(answers):
	l = 0
	r = int(input()) - 1
	numbers = [int(x) for x in input().split()]
	marginals = []
	while l < r:
		if numbers[l] == numbers[r]:
			l += 1
			r -= 1
		else:
			marginals += [numbers[l], numbers[r]]
			break
	marginals.append(-1)
	for x in marginals:
		tmp = [y for y in numbers if y != x]
		if tmp == list(reversed(tmp)):
			answers.append('YES')
			return
	answers.append('NO')
sets_num = int(input())
answers = []
for i in range(sets_num):
	solve(answers)
for i in answers:
	print(i)


for r in [*open(0)][2::2]:
	m = r.split()
	i = len(m)
	while i and m[i - 1] == m[-i]:
		i -= 1
	print('YNEOS'[all((z != z[::-1] for z in ([x for x in m if x != y] for y in (m[i - 1], m[-i]))))::2])


t = int(input())
A = []
for x in range(t):
	n = input()
	a = list(map(int, input().split()))
	A.append(a)
for a in A:
	(i, j) = (0, len(a))
	if j in [0, 1, 2]:
		print('YES')
	else:
		result = False
		j -= 1
		(left, right) = (None, None)
		while i < j:
			if a[i] == a[j]:
				i += 1
				j -= 1
				result = True
				continue
			elif not left:
				left = a[i]
				(l, k) = (i + 1, j)
				while l < k:
					if a[l] == a[k]:
						l += 1
						k -= 1
						result = True
						continue
					elif a[l] == left:
						l += 1
						result = True
						continue
					elif a[k] == left:
						k -= 1
						result = True
						continue
					else:
						result = False
						break
			elif not right and (not result):
				right = a[j]
				(l, k) = (i, j - 1)
				while l < k:
					if a[l] == a[k]:
						l += 1
						k -= 1
						result = True
						continue
					elif a[l] == right:
						l += 1
						result = True
						continue
					elif a[k] == right:
						k -= 1
						result = True
						continue
					else:
						result = False
						break
			else:
				break
		if result:
			print('YES')
		else:
			print('NO')


import sys
import math
from bisect import bisect_right as br
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()

def finding():
	i = 0
	j = n - 1
	while i < j:
		if arr[i] == arr[j]:
			i += 1
			j -= 1
		else:
			return [i, j]
	return 0

def ch(val, i, j):
	while i < j:
		if arr[i] == arr[j]:
			i += 1
			j -= 1
		elif arr[i] == val:
			i += 1
		elif arr[j] == val:
			j -= 1
		else:
			return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	v = finding()
	if v == 0:
		print('YES')
		continue
	(i, j) = v
	z = i
	y = j
	val1 = arr[i]
	val2 = arr[j]
	a = ch(val1, i, j)
	b = ch(val2, z, y)
	if a == 1 or b == 1:
		print('YES')
	else:
		print('NO')


def check_new(a, i, j, k):
	while i < j:
		if a[i] == k:
			i += 1
		elif a[j] == k:
			j -= 1
		elif a[i] == a[j]:
			(i, j) = (i + 1, j - 1)
		else:
			return False
	return True

def check_palindrome(a, i, j):
	while i < j:
		if a[i] != a[j]:
			return check_new(a, i, j - 1, a[j]) or check_new(a, i + 1, j, a[i])
		else:
			(i, j) = (i + 1, j - 1)
	return True
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	if check_palindrome(a, 0, n - 1):
		print('YES')
	else:
		print('NO')
	t -= 1


import sys
import math
from fractions import Fraction
from decimal import *
input = sys.stdin.readline

def checkPalin(arr, l, r, num):
	while l < r:
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		elif arr[l] == num:
			l += 1
		elif arr[r] == num:
			r -= 1
		else:
			return False
	return True
t = int(input())
while t > 0:
	n = int(input().strip())
	inp = input().strip()
	arr = [int(x) for x in inp.split(' ')]
	l = 0
	r = len(arr) - 1
	while l < r:
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		else:
			break
	if arr[l] == arr[r]:
		print('YES')
	else:
		a = checkPalin(arr, l + 1, r, arr[l])
		if a:
			print('YES')
		else:
			a = checkPalin(arr, l, r - 1, arr[r])
			if a:
				print('YES')
			else:
				print('NO')
	t -= 1


def f(i, j, remove, A):
	while i < j:
		if A[i] == remove:
			i += 1
		elif A[j] == remove:
			j -= 1
		elif A[i] == A[j]:
			i += 1
			j -= 1
		else:
			return False
	return True

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	(i, j) = (0, len(A) - 1)
	while i < j and A[i] == A[j]:
		i += 1
		j -= 1
	if i >= j:
		return True
	choice_one = f(i + 1, j, A[i], A)
	if choice_one:
		return True
	choice_two = f(i, j - 1, A[j], A)
	return choice_two
for _ in range(int(input())):
	if solve():
		print('YES')
	else:
		print('NO')


from math import ceil, floor, log
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())

def palind(arr, x):
	l = [i for i in arr if i != x]
	if l == l[::-1]:
		return 1
	return 0
for _ in range(int(input().strip())):
	n = inp_int()
	a = inp_lis()
	if a == a[::-1] or n == 2 or n == 1:
		print('YES')
		continue
	ans = 1
	i = 0
	while i < n - i:
		if a[i] != a[n - i - 1]:
			ans = max(palind(a, a[i]), palind(a, a[n - i - 1]))
			break
		i += 1
	if ans == 0:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	ans = 'NO'
	for i in range(n // 2):
		if w[i] != w[n - 1 - i]:
			s = w[i:n - i]
			d = [a for a in s if a != w[i]]
			x = len(d)
			e = [a for a in s if a != w[n - 1 - i]]
			y = len(e)
			for j in range(x // 2):
				if d[j] != d[x - 1 - j]:
					break
			else:
				ans = 'YES'
			if ans == 'NO':
				for j in range(y // 2):
					if e[j] != e[y - 1 - j]:
						break
				else:
					ans = 'YES'
			break
	else:
		ans = 'YES'
	print(ans)


def check(x):
	l = 0
	r = n - 1
	while l <= r:
		if a[l] == x:
			l += 1
			continue
		if a[r] == x:
			r -= 1
			continue
		if a[l] == a[r]:
			l += 1
			r -= 1
			continue
		return False
	return True
T = int(input())
for tests in range(T):
	n = int(input())
	S = input()
	a = S.split()
	l = 0
	r = n - 1
	while l <= r:
		if a[l] != a[r]:
			break
		else:
			l += 1
			r -= 1
	if l >= r:
		print('YES')
		continue
	if check(a[l]) or check(a[r]):
		print('YES')
	else:
		print('NO')


def pal(a, n1, n2, n, c):
	while n1 < n2 and n1 < n:
		if a[n1] == a[n2]:
			n1 += 1
			n2 -= 1
		elif a[n1] == c:
			n1 += 1
		elif a[n2] == c:
			n2 -= 1
		else:
			return False
	return True

def pa(a, n):
	n1 = 0
	n2 = n - 1
	while n1 < n2:
		if a[n1] == a[n2]:
			n1 += 1
			n2 -= 1
		else:
			if pal(a, n1 + 1, n2, n, a[n1]):
				return 'YES'
			elif pal(a, n1, n2 - 1, n, a[n2]):
				return 'YES'
			else:
				return 'NO'
			break
	return 'YES'
t = int(input())
for tt in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	if n == 1 or n == 2:
		print('YES')
	else:
		print(pa(ar, n))


def is_kalindrome(a, n):
	i = 0
	j = n - 1
	x = -1
	flag = 0
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		else:
			if flag == 0:
				k = i + 1
				x = a[i]
				while a[k] == x:
					k += 1
				if a[k] == a[j]:
					i = k + 1
					j -= 1
					flag = 1
					continue
				h = j - 1
				x = a[j]
				while a[h] == x:
					h -= 1
				if a[h] == a[i]:
					i += 1
					j = h - 1
					flag = 1
					continue
				return False
			elif flag == 1 and x == a[i]:
				while a[i] == x:
					i += 1
				if a[i] == a[j]:
					i += 1
					j -= 1
					continue
				return False
			elif flag == 1 and x == a[j]:
				while a[j] == x:
					j -= 1
				if a[i] == a[j]:
					i += 1
					j -= 1
					continue
				return False
			return False
	return True
n_testcase = int(input())
for _ in range(n_testcase):
	n = int(input())
	a = list(map(int, input().split()))
	if is_kalindrome(a, n):
		print('YES')
	else:
		print('NO')


from tkinter.messagebox import RETRY

def IsFixable(a, l, r, av_to_rem):
	while l <= r:
		if a[l] == a[r]:
			l += 1
			r -= 1
		elif a[l] == av_to_rem:
			l += 1
		elif a[r] == av_to_rem:
			r -= 1
		else:
			return False
	return True

def SolOfTest(n, a):
	(l, r) = (0, n - 1)
	while l <= r and a[l] == a[r]:
		l += 1
		r -= 1
	if l > r:
		return 'YES'
	is_fixable = IsFixable(a, l, r, a[l]) or IsFixable(a, l, r, a[r])
	if is_fixable:
		return 'YES'
	else:
		return 'NO'

def GetInputOfTest():
	n = int(input())
	a = list(map(int, input().split()))
	return (n, a)
num_tests = int(input())
answers = []
for test_ind in range(num_tests):
	(n, a) = GetInputOfTest()
	answ = SolOfTest(n, a)
	answers.append(answ)
for answ in answers:
	print(answ)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))

	def fun(l):
		(i, j) = (0, n - 1)
		while i < j:
			if l[i] != l[j]:
				break
			i += 1
			j -= 1
		if i >= j:
			return 'YES'
		(a, b) = (i, j)
		(i, j) = (0, n - 1)
		while i < j:
			if l[i] != l[j]:
				if l[i] == l[a]:
					i += 1
				elif l[j] == l[a]:
					j -= 1
				else:
					break
			else:
				i += 1
				j -= 1
		if i >= j:
			return 'YES'
		(i, j) = (0, n - 1)
		while i < j:
			if l[i] != l[j]:
				if l[i] == l[b]:
					i += 1
				elif l[j] == l[b]:
					j -= 1
				else:
					break
			else:
				i += 1
				j -= 1
		if i >= j:
			return 'YES'
		return 'NO'
	print(fun(l))


import copy
import math
from sys import stdin

def A():
	t = int(stdin.readline())
	while t:
		t -= 1
		(n, m) = [int(x) for x in stdin.readline().split()]
		if n == 1 and m == 1:
			print(0)
		else:
			print(min(n, m))

def B():
	t = int(stdin.readline())
	while t:
		t -= 1
		n = int(stdin.readline())
		a = [int(x) for x in stdin.readline().split()]
		res = []
		res1 = []
		l = 0
		r = n - 1
		while a[l] == a[r] and l < r:
			l += 1
			r -= 1
		for i in a:
			if i == a[l]:
				continue
			res.append(i)
		for i in a:
			if i == a[r]:
				continue
			res1.append(i)
		if res == res[::-1] or len(res) == 0:
			print('YES')
		elif res1 == res1[::-1] or len(res1) == 0:
			print('YES')
		else:
			print('NO')

def C():
	t = int(stdin.readline())
	while t:
		t -= 1
		a = [int(x) for x in stdin.readline().split()]
		(n, m) = (a[0], a[1])
		m1 = copy.deepcopy(m)
		m += 1
		res = n ^ m
		while res >= m1:
			m += 1
			res = n ^ m
		while n ^ m < m1:
			m += 1
			res = min(n ^ m, res)
		print(res)

def D():
	t = int(stdin.readline())
	while t:
		t -= 1
B()


def sl(s, rem):
	tes = []
	for val in s:
		if val != rem:
			tes.append(val)
	return tes == tes[::-1]

def solve(s, i, j):
	while i <= j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			return sl(s, s[i]) or sl(s, s[j])
	return True
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if solve(arr, 0, n - 1):
		print('YES')
	else:
		print('NO')


t = int(input())

def ispalin(a):
	i = 0
	j = len(a) - 1
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
			continue
		else:
			return (a[i], a[j])
	return (-1, -1)

def ispalinwox(a, x):
	i = 0
	j = len(a) - 1
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
			continue
		elif a[i] == x:
			i += 1
			continue
		elif a[j] == x:
			j -= 1
			continue
		else:
			return False
	return True
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('YES')
		continue
	(poss1, poss2) = ispalin(a)
	if poss1 == -1:
		print('YES')
		continue
	if ispalinwox(a, poss1) or ispalinwox(a, poss2):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))

	def check(i, j, x):
		while i < j:
			if arr[i] != arr[j]:
				if x != -1:
					if arr[i] != x and arr[j] != x:
						return False
					if arr[i] == x:
						i += 1
					else:
						j -= 1
				else:
					return check(i + 1, j, arr[i]) or check(i, j - 1, arr[j])
			else:
				i += 1
				j -= 1
		return True
	print('YES' if check(0, n - 1, -1) else 'NO')


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(str, input().strip().split()))
mod = 1000000007

def valid(arr, l, r, var):
	flag = 1
	while l < r:
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		elif arr[l] == var:
			l += 1
		elif arr[r] == var:
			r -= 1
		else:
			flag = 0
			break
	return flag
for _ in range(I()):
	n = I()
	a = L()
	(i, j) = (0, len(a) - 1)
	flag = 1
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		else:
			if not (valid(a, i + 1, j, a[i]) or valid(a, i, j - 1, a[j])):
				flag = 0
			break
	print('YES' if flag else 'NO')


def kalindrome(arr, length):
	left = 0
	right = length - 1
	if checkPalindrome(arr, left, right, 0):
		return True
	while left < right:
		if arr[left] != arr[right]:
			checkLeft = checkPalindrome(arr, left + 1, right, arr[left])
			checkRight = checkPalindrome(arr, left, right - 1, arr[right])
			if checkLeft or checkRight:
				return True
			else:
				return False
		left += 1
		right -= 1
	return False

def checkPalindrome(arr, left, right, k):
	while left < right:
		if arr[left] == k or arr[right] == k:
			if arr[left] == k:
				left += 1
			if arr[right] == k:
				right -= 1
		else:
			if arr[right] != arr[left]:
				return False
			left += 1
			right -= 1
	return True

def checkKalindrome(arr, length):
	check = kalindrome(arr, length)
	if check:
		return 'YES'
	return 'NO'
case = int(input())
for i in range(case):
	length = int(input())
	arr = list(map(int, input().split(' ')))
	print(checkKalindrome(arr, length))


def check(numbers, number):
	new_numbers = [x for x in numbers if x != number]
	return new_numbers == new_numbers[::-1]

def main():
	n = int(input())
	numbers = [int(x) for x in input().split()]
	for i in range(n // 2):
		if numbers[i] != numbers[n - i - 1]:
			if check(numbers, numbers[i]) or check(numbers, numbers[n - i - 1]):
				return 'YES'
			return 'NO'
	return 'YES'
tests = int(input())
while tests:
	tests -= 1
	print(main())


from collections import defaultdict

def isKalindrome(arr, size, dell):
	fp = 0
	lp = size - 1
	while fp <= lp:
		if arr[lp] != arr[fp]:
			if arr[fp] == dell:
				lp += 1
			elif arr[lp] == dell:
				fp -= 1
			else:
				return False
		fp += 1
		lp -= 1
	return True

def func(arr):
	(fp, lp) = (0, len(arr) - 1)
	isKal = True
	while fp <= lp:
		if arr[fp] != arr[lp]:
			if not (isKalindrome(arr, len(arr), arr[fp]) or isKalindrome(arr, len(arr), arr[lp])):
				isKal = False
				break
			else:
				isKal = True
				break
		fp += 1
		lp -= 1
	if isKal:
		return 'YES'
	else:
		return 'NO'
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	print(func(arr))


get_int = lambda : int(input())
get_int_list = lambda : list(map(int, input().split()))

def solve():
	n = get_int()
	ar = get_int_list()
	left = 0
	right = n - 1
	while left <= right:
		if ar[left] != ar[right]:
			break
		left += 1
		right -= 1
	if left > right:
		print('YES')
		return
	saved = (left, right)
	for x in [ar[left], ar[right]]:
		(left, right) = saved
		while left <= right:
			if ar[left] == x:
				left += 1
			elif ar[right] == x:
				right -= 1
			elif ar[left] == ar[right]:
				left += 1
				right -= 1
			else:
				break
		found_x = left > right
		if found_x:
			break
	if found_x:
		print('YES')
	else:
		print('NO')
t = get_int()
for _ in range(t):
	solve()


def remove(i, j, x):
	ans = True
	while i <= j:
		if a[i] != a[j]:
			if a[i] == x:
				i += 1
			elif a[j] == x:
				j -= 1
			else:
				ans = False
				break
		else:
			i += 1
			j -= 1
	return ans
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(i, j) = (0, n - 1)
	while i <= j and a[i] == a[j]:
		i += 1
		j -= 1
	ans = True
	if i > j:
		print('YES')
		continue
	if remove(i, j, a[i]) or remove(i, j, a[j]):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	kal = list(map(int, input().split()))
	i = 0
	j = n - 1
	ignore = -1
	flag = 0
	flag2 = 0
	while i < j:
		if kal[i] == kal[j]:
			i += 1
			j -= 1
		else:
			if flag == 0:
				ignore = kal[i]
				i += 1
				flag = 1
				continue
			if kal[i] == ignore:
				i += 1
			elif kal[j] == ignore:
				j -= 1
			else:
				flag2 = 1
				break
	flag3 = 0
	i = 0
	j = n - 1
	flag = 0
	while i < j:
		if kal[i] == kal[j]:
			i += 1
			j -= 1
		else:
			if flag == 0:
				ignore = kal[j]
				j -= 1
				flag = 1
				continue
			if kal[i] == ignore:
				i += 1
			elif kal[j] == ignore:
				j -= 1
			else:
				flag3 = 1
				break
	if (flag2 and flag3) == 0:
		print('YES')
	else:
		print('NO')


def remove(l, item):
	res = list(filter(item.__ne__, l))
	n1 = len(res)
	l1 = res[:n1 // 2]
	r1 = res[n1 - n1 // 2:]
	r1 = r1[::-1]
	if l1 == r1:
		return 1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 2:
		print('YES')
		continue
	f = 1
	for i in range(n // 2):
		if a[i] != a[n - 1 - i]:
			if remove(a, a[i]) or remove(a, a[n - 1 - i]):
				print('YES')
				f = 0
				break
			else:
				print('NO')
				f = 0
				break
	if f:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a == a[::-1]:
		print('YES')
		continue
	aa = a[::-1]
	for i in range(n):
		if a[i] != aa[i]:
			badchar = a[i]
			badchar2 = aa[i]
			b = [i for i in a if i != badchar]
			bb = [i for i in a if i != badchar2]
			if b == b[::-1] or bb == bb[::-1]:
				print('YES')
			else:
				print('NO')
			break


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	while n and arr[n - 1] == arr[-n]:
		n -= 1
	print('YNEOS'[all((v != v[::-1] for v in ([x for x in arr if x != y] for y in (arr[n - 1], arr[-n]))))::2])


def is_kalindrome(a, x):
	i = 0
	j = len(a) - 1
	orig_x = x
	if j <= 0:
		return True
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
			continue
		else:
			orig_i = i
			if not x:
				x = a[i]
			while x and i < j and (a[i] == x):
				i += 1
			if i != orig_i and is_kalindrome(a[i:j + 1], x):
				return True
			x = orig_x
			if not x:
				x = a[j]
			i = orig_i
			orig_j = j
			while x and i < j and (a[j] == x):
				j -= 1
			if j != orig_j and is_kalindrome(a[i:j + 1], x):
				return True
			return False
	return True

def main():
	no_of_test_cases = int(input().strip())
	for i in range(no_of_test_cases):
		n = int(input().strip())
		a = list(map(int, input().strip().split()))
		if is_kalindrome(a, None):
			print('YES')
		else:
			print('NO')
main()


def ispalindrome(arr):
	return arr == arr[::-1]

def removeall(arr, x):
	return [i for i in arr if i != x]

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	(i, j) = (0, n - 1)
	while i < j:
		if arr[i] != arr[j]:
			if ispalindrome(removeall(arr, arr[i])) or ispalindrome(removeall(arr, arr[j])):
				return 'YES'
			return 'NO'
		i += 1
		j -= 1
	return 'YES'
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	vals = None
	for i in range(n):
		if a[i] != a[-i - 1]:
			vals = (a[i], a[-i - 1])
			break
	else:
		print('YES')
		continue
	b = a.copy()
	b = [x for x in a if x != vals[0]]
	a = [x for x in a if x != vals[-1]]
	if b == b[::-1] or a == a[::-1]:
		print('YES')
	else:
		print('NO')


def isPalindrome(x):
	if x == x[::-1]:
		return True
	return False
_ = int(input())
for __ in range(_):
	n = int(input())
	arr = list(map(int, input().split()))
	if isPalindrome(arr):
		print('YES')
	else:
		beg = 0
		end = n - 1
		while beg < end:
			if arr[beg] == arr[end]:
				beg += 1
				end -= 1
			else:
				if isPalindrome([x for x in arr if x != arr[beg]]) or isPalindrome([x for x in arr if x != arr[end]]):
					print('YES')
				else:
					print('NO')
				break


I = input
for _ in range(int(I())):
	n = int(I())
	lst = list(map(int, I().split()))
	i = 0
	while 2 * i < n - 1 and lst[i] == lst[-i - 1]:
		i += 1
	for y in (lst[i], lst[-i - 1]):
		v = [x for x in lst if x != y]
		if v == v[::-1]:
			print('YES')
			break
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	check = False
	ck = False
	num = -1
	i = 0
	j = n - 1
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		elif a[i] != a[j] and (not ck):
			num = a[j]
			ck = True
			j -= 1
		elif a[i] != a[j] and ck:
			if a[i] == num:
				i += 1
			elif a[j] == num:
				j -= 1
			else:
				check = True
				break
		if check:
			break
	ck = False
	num = -1
	if check:
		check = False
		i = 0
		j = n - 1
		while i < j:
			if a[i] == a[j]:
				i += 1
				j -= 1
			elif a[i] != a[j] and (not ck):
				num = a[i]
				ck = True
				i += 1
			elif a[i] != a[j] and ck:
				if a[i] == num:
					i += 1
				elif a[j] == num:
					j -= 1
				else:
					check = True
					break
			if check:
				break
		if check:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('YES')
		continue
	if n == 2:
		print('YES')
		continue
	i = 0
	j = n - 1
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		else:
			break
	if i >= j:
		print('YES')
		continue
	(p, q) = (i, j)
	(x, y) = (a[i], a[j])
	i += 1
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		elif a[i] == x:
			i += 1
		elif a[j] == x:
			j -= 1
		else:
			break
	if i >= j:
		print('YES')
		continue
	(i, j) = (p, q)
	j -= 1
	while i < j:
		if a[i] == a[j]:
			i += 1
			j -= 1
		elif a[i] == y:
			i += 1
		elif a[j] == y:
			j -= 1
		else:
			break
	if i >= j:
		print('YES')
		continue
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = 0
	r = n - 1
	if l == r:
		print('YES')
		continue
	while l < r:
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		else:
			d1 = arr[l]
			d2 = arr[r]
			break
	if l >= r:
		print('YES')
		continue
	(l, r) = (0, n - 1)
	while l < r:
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		elif arr[l] == d1:
			l += 1
		elif arr[r] == d1:
			r -= 1
		else:
			break
	if l >= r:
		print('YES')
		continue
	(l, r) = (0, n - 1)
	while l < r:
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		elif arr[l] == d2:
			l += 1
		elif arr[r] == d2:
			r -= 1
		else:
			break
	if l >= r:
		print('YES')
		continue
	print('NO')


def ispalindrome(arr):
	return arr == arr[::-1]

def iskalindrome(arr, n):
	i = 0
	j = n - 1
	while i < j:
		if arr[i] != arr[j]:
			arr1 = []
			arr2 = []
			for k in arr:
				if k == arr[i]:
					arr2.append(k)
				elif k == arr[j]:
					arr1.append(k)
				else:
					arr2.append(k)
					arr1.append(k)
			if ispalindrome(arr2) or ispalindrome(arr1):
				return 1
			else:
				return 0
		i += 1
		j -= 1
	return 1
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print('YES' if iskalindrome(arr, n) else 'NO')


remove = lambda x, a: [i for i in a if i != x]
for _ in range(int(input())):
	(n, ans) = (int(input()), 0)
	l = list(map(int, input().split()))
	for i in range(len(l)):
		if l[i] != l[n - 1 - i]:
			if (z := remove(l[i], l)) != z[::-1] and (z := remove(l[n - 1 - i], l)) != z[::-1]:
				ans = 1
			break
	print('YNEOS'[ans::2])


def f(a, bad):
	n = len(a)
	(i, j) = (0, n - 1)
	while i < j:
		if a[i] == bad:
			i += 1
		elif a[j] == bad:
			j -= 1
		elif a[i] != a[j]:
			return False
		else:
			i += 1
			j -= 1
	return True
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(i, j) = (0, n - 1)
	bad = None
	while i < j:
		if a[i] != a[j]:
			bad = [a[i], a[j]]
			break
		else:
			i += 1
			j -= 1
	if bad is None:
		print('YES')
		continue
	for x in bad:
		if f(a, x):
			print('YES')
			break
	else:
		print('NO')


def func(arr, val):
	arr1 = list(filter(val.__ne__, arr))
	return arr1 == arr1[::-1]

def solve(arr):
	i = 0
	j = len(arr) - 1
	k = 0
	while i <= j:
		if arr[i] == arr[j]:
			i += 1
			j -= 1
		else:
			ans1 = func(arr, arr[i])
			ans2 = func(arr, arr[j])
			if not ans1 and (not ans2):
				return False
			if ans1 or ans2:
				return True
	return True
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	if solve(arr):
		print('YES')
		t -= 1
	else:
		print('NO')
		t -= 1


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	flag = False
	if n <= 2 or array == array[::-1]:
		flag = True
	else:
		i = 0
		j = n - 1
		while i <= j:
			if array[i] != array[j]:
				a1 = [x for x in array if x != array[i]]
				a2 = [x for x in array if x != array[j]]
				if a1 == a1[::-1] or a2 == a2[::-1]:
					flag = True
				else:
					flag = False
				break
			i += 1
			j -= 1
	if flag:
		print('YES')
	else:
		print('NO')


def test(A, x):
	(a, b) = (0, len(A) - 1)
	while a < b:
		if A[a] == A[b]:
			a += 1
			b -= 1
		elif A[a] == x:
			a += 1
		elif A[b] == x:
			b -= 1
		else:
			return False
	return True

def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	(a, b) = (0, len(A) - 1)
	while a < b:
		if A[a] == A[b]:
			a += 1
			b -= 1
		elif test(A, A[a]) or test(A, A[b]):
			return 'YES'
		else:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	j = n - 1
	k = 0
	ans1 = 1
	ans2 = 1
	while i < j:
		if a[i] != a[j] and k == 0:
			a1 = a[i]
			b = a[j]
			k = 1
		if k == 1:
			if a[i] == a[j]:
				i += 1
				j -= 1
			elif a[i] == a1:
				i += 1
			elif a[j] == a1:
				j -= 1
			else:
				ans1 = 0
				k += 1
				i = 0
				j = n - 1
			if i > j:
				i = 0
				j = n - 1
				k += 1
		elif k == 2:
			if a[i] == a[j]:
				i += 1
				j -= 1
			elif a[i] == b:
				i += 1
			elif a[j] == b:
				j -= 1
			else:
				ans2 = 0
				break
		else:
			i += 1
			j -= 1
	if ans1 == 1 or ans2 == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for q in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	left = 0
	right = n - 1
	flag = 0
	x = None
	while left < right:
		if flag:
			break
		if arr[left] == arr[right]:
			left += 1
			right -= 1
		elif x:
			if x == arr[left]:
				left += 1
			elif x == arr[right]:
				right -= 1
			else:
				flag = 1
				break
		else:
			x = arr[left]
			left += 1
	l = 0
	r = n - 1
	f = 0
	y = None
	while l < r:
		if f:
			break
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		elif y:
			if y == arr[l]:
				l += 1
			elif y == arr[r]:
				r -= 1
			else:
				f = 1
				break
		else:
			y = arr[r]
			r -= 1
	if f * flag:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a == a[::-1]:
		print('YES')
	else:
		for i in range(n // 2):
			if a[i] != a[n - 1 - i]:
				(t, b) = (a[i], a[n - 1 - i])
				break
		for j in [t, b]:
			p = [i for i in a if i != j]
			if p == p[::-1]:
				print('YES')
				break
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a == a[::-1]:
		print('YES')
		continue
	for i in range(n // 2):
		if a[i] != a[n - i - 1]:
			(x, y) = (a[i], a[n - i - 1])
			break
	a1 = [i for i in a if i != x]
	a2 = [i for i in a if i != y]
	if a1 == a1[::-1] or a2 == a2[::-1]:
		print('YES')
		continue
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	while arr[i] == arr[n - i - 1]:
		i += 1
		if i == n:
			break
	if i == n:
		print('YES')
		continue
	p = arr[i]
	l = i + 1
	r = n - i - 1
	while l < r:
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		elif arr[l] == p:
			l += 1
		elif arr[r] == p:
			r -= 1
		else:
			break
	if l >= r:
		print('YES')
		continue
	p = arr[n - i - 1]
	l = i
	r = n - i - 2
	while l < r:
		if arr[l] == arr[r]:
			l += 1
			r -= 1
		elif arr[l] == p:
			l += 1
		elif arr[r] == p:
			r -= 1
		else:
			break
	if l >= r:
		print('YES')
		continue
	print('NO')


def works(a, k):
	s = 0
	e = len(a) - 1
	while s < e:
		if arr[s] == arr[e]:
			s += 1
			e -= 1
		elif arr[s] == k:
			s += 1
		elif arr[e] == k:
			e -= 1
		else:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr == arr[::-1]:
		print('YES')
		continue
	i = 0
	j = n - 1
	while i < j:
		if arr[i] == arr[j]:
			i += 1
			j -= 1
		else:
			if works(arr, arr[i]) or works(arr, arr[j]):
				print('YES')
			else:
				print('NO')
			break


def palindrome(a, n, num):
	left = 0
	right = n - 1
	while left < right:
		while left <= right and a[left] == num:
			left += 1
		while right >= left and a[right] == num:
			right -= 1
		if a[left] != a[right]:
			return False
		else:
			left += 1
			right -= 1
	return True

def Kalindrome_Array(a, n):
	if n == 1 or n == 2:
		return 'YES'
	l = 0
	r = n - 1
	while l < r:
		if a[l] != a[r]:
			if palindrome(a, n, a[l]) or palindrome(a, n, a[r]):
				return 'YES'
			else:
				return 'NO'
		else:
			l += 1
			r -= 1
	return 'YES'
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(Kalindrome_Array(a, n))


import sys

def isPalindrome(arr):
	if len(arr) % 2 == 0:
		r = len(arr) // 2
	else:
		r = len(arr) // 2 + 1
	for i in range(r):
		if arr[i] != arr[len(arr) - 1 - i]:
			return (False, arr[i], arr[len(arr) - 1 - i])
	return (True, None, None)
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	arr = [int(x) for x in sys.stdin.readline().split()]
	(res, x1, x2) = isPalindrome(arr)
	if not res:
		list_1 = [x for x in arr if x != x1]
		(res, _, _) = isPalindrome(list_1)
	if not res:
		list_2 = [x for x in arr if x != x2]
		(res, _, _) = isPalindrome(list_2)
	print('YES' if res else 'NO')


def isPalin(x):
	if x == x[::-1]:
		return True
	return False
t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	if isPalin(a):
		print('YES')
		t -= 1
		continue
	for i in range(n // 2):
		if a[i] != a[n - i - 1]:
			k1 = a[i]
			k2 = a[n - i - 1]
			break
	net1 = [i for i in a if i != k1]
	net2 = [i for i in a if i != k2]
	if isPalin(net1) or isPalin(net2):
		print('YES')
	else:
		print('NO')
	t -= 1


for j in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	el = -1
	ell = -1
	dis = n // 2
	if n % 2 == 1:
		dis += 1
	for i in range(dis):
		if arr[i] != arr[n - i - 1]:
			el = arr[n - i - 1]
			ell = arr[i]
			break
	(a, b) = ([], [])
	for i in arr:
		if el != i:
			a.append(i)
		if ell != i:
			b.append(i)
	if a == a[::-1] or b == b[::-1]:
		print('YES')
		continue
	print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	flag = 1
	(i, j, k) = (0, n - 1, 0)
	while i < j:
		if l[i] == l[j]:
			pass
		elif k == 0:
			k = l[j]
			j -= 1
			continue
		elif k == l[j]:
			j -= 1
			continue
		elif k == l[i]:
			i += 1
			continue
		else:
			flag = 0
			break
		i += 1
		j -= 1
	f2 = 1
	(i, j, k) = (0, n - 1, 0)
	while i < j:
		if l[i] == l[j]:
			pass
		elif k == 0:
			k = l[i]
			i += 1
			continue
		elif k == l[i]:
			i += 1
			continue
		elif k == l[j]:
			j -= 1
			continue
		else:
			f2 = 0
			break
		i += 1
		j -= 1
	if not (flag or f2):
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	(x, y, cnt) = (0, 0, 0)
	a = [int(j) for j in input().split()]
	(start, stop) = (0, n - 1)
	while start <= stop:
		if a[start] != a[stop] and cnt == 0:
			y = stop
			stop -= 1
			cnt += 1
			continue
		if a[start] == a[stop]:
			start += 1
			stop -= 1
		elif a[start] == a[y]:
			start += 1
		elif a[stop] == a[y]:
			stop -= 1
		else:
			break
	else:
		print('YES')
		continue
	(start, stop, cnt) = (0, n - 1, 0)
	while start <= stop:
		if a[start] != a[stop] and cnt == 0:
			x = start
			start += 1
			cnt += 1
			continue
		if a[start] == a[stop]:
			start += 1
			stop -= 1
		elif a[start] == a[x]:
			start += 1
		elif a[stop] == a[x]:
			stop -= 1
		else:
			break
	else:
		print('YES')
		continue
	if start <= stop:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	ns = list(map(int, input().split()))
	nums = []
	for i in range(n // 2):
		(l, r) = (ns[i], ns[-1 - i])
		if l == r:
			continue
		nums = [l, r]
		break
	if not nums:
		print('YES')
		continue
	for num in nums:
		(li, ri) = (0, n - 1)
		ok = True
		while li < ri:
			(l, r) = (ns[li], ns[ri])
			if l == r:
				li += 1
				ri -= 1
				continue
			if l == num:
				li += 1
			elif r == num:
				ri -= 1
			else:
				ok = False
				break
		if ok:
			break
	if ok:
		print('YES')
	else:
		print('NO')


def ch(a, n, z):
	l = 1
	r = n
	while l <= r:
		if z[l] == z[r]:
			l += 1
			r -= 1
		elif z[l] != a and z[r] != a:
			return False
		elif z[l] == a:
			l += 1
		elif z[r] == a:
			r -= 1
	return True
t = int(input())
for i in range(t):
	n = int(input())
	(a, b) = (0, 0)
	z = list(map(int, input().split()))
	z.insert(0, 0)
	for j in range(1, n // 2 + 1):
		if z[j] != z[n + 1 - j]:
			a = z[j]
			b = z[n + 1 - j]
			break
	if ch(a, n, z) or ch(b, n, z):
		print('YES')
	else:
		print('NO')
	z = []


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	if n <= 1:
		print('YES')
	elif n == 3:
		if len(set(x)) <= 2:
			print('YES')
		else:
			print('NO')
	else:
		ans = 'YES'
		temp = []
		for k in range(n // 2):
			if x[k] != x[n - 1 - k]:
				ans = 'NO'
				temp += [x[k], x[n - 1 - k]]
				break
		if ans == 'NO':
			for j in range(2):
				l = k
				r = n - 1 - k
				while l < r:
					if x[l] != x[r]:
						if x[l] == temp[j]:
							l += 1
						elif x[r] == temp[j]:
							r -= 1
						else:
							break
					elif x[l] == x[r]:
						l += 1
						r -= 1
					if l >= r:
						ans = 'YES'
						break
						break
		print(ans)


t = int(input())

def palindrome(val):
	for (i, v) in enumerate(val[:len(val) // 2]):
		opp = val[len(val) - 1 - i]
		if v != opp:
			return False
	return True
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if palindrome(arr) or n == 1:
		print('YES')
		continue
	for (i, v) in enumerate(arr):
		opp = arr[n - 1 - i]
		if v != opp:
			first = [x for x in arr if x != v]
			second = [x for x in arr if x != opp]
			if palindrome(first) or palindrome(second):
				print('YES')
			else:
				print('NO')
			break


def check(arr, x):
	i = 0
	j = len(arr) - 1
	while i < j:
		if arr[i] == x:
			i += 1
		elif arr[j] == x:
			j -= 1
		elif arr[i] != arr[j]:
			return 0
		else:
			i += 1
			j -= 1
	return 1
testCase = int(input())
while testCase != 0:
	testCase -= 1
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	flag = 1
	for i in range(0, n - 1):
		if arr[i] != arr[n - 1 - i]:
			flag = check(arr, arr[i]) or check(arr, arr[n - 1 - i])
			break
	print('YES' if flag else 'NO')


from typing import Iterable

def filter_list(a: Iterable[int], remove_value: int) -> Iterable[int]:
	return [i for i in a if i != remove_value]

def is_palindrom(a: Iterable[int]) -> bool:
	for i in range((len(a) + 1) // 2):
		if a[i] != a[-i - 1]:
			return False
	return True

def Solution() -> str:
	n = int(input())
	a = list(map(int, input().split()))
	for i in range((n + 1) // 2):
		if a[i] != a[-i - 1]:
			if is_palindrom(filter_list(a, a[i])) or is_palindrom(filter_list(a, a[-i - 1])):
				return 'YES'
			else:
				return 'NO'
	return 'YES'
t = int(input())
for i in range(t):
	print(Solution())


def check(x):
	a = []
	for i in range(n):
		if l[i] != x:
			a.append(l[i])
	if a[:] != a[::-1]:
		return False
	else:
		return True
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	ok = 1
	for i in range(n):
		if l[i] != l[n - i - 1]:
			ok = 0
			if check(l[i]):
				ok = 1
			if check(l[n - i - 1]):
				ok = 1
			break
	if ok:
		print('YES')
	else:
		print('NO')


t = int(input())

def calc():
	n = int(input())
	l = list(map(int, input().split()))
	start = 0
	end = n - 1
	for j in range(n // 2):
		if l[start] == l[end]:
			start += 1
			end -= 1
		else:
			temp1 = list(filter(lambda x: x != l[start], l))
			temp2 = list(filter(lambda x: x != l[end], l))
			if temp1 == temp1[::-1] or temp2 == temp2[::-1]:
				return 'YES'
			else:
				return 'NO'
	return 'YES'
for i in range(t):
	print(calc())


def check(num, nums):
	b = []
	for i in range(len(nums)):
		if nums[i] != num:
			b.append(nums[i])
	if b == b[::-1]:
		return True
	else:
		return False
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	flag = True
	for i in range(n):
		if nums[i] != nums[n - 1 - i]:
			if check(nums[i], nums) or check(nums[n - i - 1], nums):
				flag = True
			else:
				flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	vals = None
	for i in range(n):
		if arr[i] != arr[-i - 1]:
			vals = (arr[i], arr[-i - 1])
			break
	else:
		print('YES')
		continue
	arr2 = [x for x in arr if x != vals[0]]
	arr = [x for x in arr if x != vals[-1]]
	if arr2 == arr2[::-1] or arr == arr[::-1]:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	si = 0
	sf = len(a) - 1
	num = -1
	check = True
	while si < sf and check:
		if a[si] != a[sf] and num == -1:
			num = a[sf]
			sf -= 1
		elif a[si] != a[sf]:
			if a[si] == num:
				si += 1
			elif a[sf] == num:
				sf -= 1
			else:
				check = False
		else:
			si += 1
			sf -= 1
	if not check:
		check = True
		si = 0
		sf = len(a) - 1
		num = -1
		while si < sf and check:
			if a[si] != a[sf] and num == -1:
				num = a[si]
				si += 1
			elif a[si] != a[sf]:
				if a[si] == num:
					si += 1
				elif a[sf] == num:
					sf -= 1
				else:
					check = False
			else:
				si += 1
				sf -= 1
	if not check:
		print('NO')
	else:
		print('YES')


import io, os, sys
t = int(input())

def GO_LIFE():
	n = int(input())
	d = list(map(int, input().split()))
	x = -1
	ans = 0
	n1 = n
	d1 = []
	for i in d:
		d1 += [i]
	i = 0
	K = 1
	k = 0
	j = 0
	while i < n // 2:
		if d[i + k] != d[-(i + K)]:
			if x == -1:
				x = d[i + k]
				y = d[-(i + K)]
				j = i
			elif d[i + k] != x and d[-(i + K)] != x:
				ans += 1
				break
			if d[i + k] != x:
				K += 1
			else:
				k += 1
			n -= 1
		else:
			i += 1
	K = 1
	k = 0
	while j < n1 // 2:
		if d1[j + k] != d1[-(j + K)]:
			if x == -1:
				x = d1[j + k]
				y = d1[-(j + K)]
			elif d1[j + k] != y and d1[-(j + K)] != y:
				ans += 1
				break
			if d1[j + k] != y:
				K += 1
			else:
				k += 1
			n1 -= 1
		else:
			j += 1
	if ans == 2:
		sys.stdout.write('NO\n')
	else:
		sys.stdout.write('YES\n')
while t > 0:
	GO_LIFE()
	t -= 1


def checkPalindrome(arr):
	left = 0
	right = len(arr) - 1
	while left < right:
		if arr[left] != arr[right]:
			return False
		left += 1
		right -= 1
	return True

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 'YES'
	left = 0
	right = len(arr) - 1
	while left < right:
		if arr[left] != arr[right]:
			break
		left += 1
		right -= 1
	firstArr = []
	secondArr = []
	for num in arr:
		if num != arr[left]:
			firstArr.append(num)
		if num != arr[right]:
			secondArr.append(num)
	if checkPalindrome(firstArr) or checkPalindrome(secondArr):
		return 'YES'
	return 'NO'
for _ in range(int(input())):
	print(solve())


for iii in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	low = 0
	high = n - 1
	flag = True
	q1 = 0
	q2 = 0
	while low <= high:
		if q[low] != q[high]:
			q1 = q[low]
			q2 = q[high]
			flag = False
			break
		low += 1
		high -= 1
	if flag:
		print('YES')
		continue
	low = 0
	high = n - 1
	flag = True
	while low <= high and flag:
		if q[low] == q1:
			low += 1
		elif q[high] == q1:
			high -= 1
		elif q[low] != q[high]:
			flag = False
		else:
			low += 1
			high -= 1
	if flag:
		print('YES')
		continue
	low = 0
	high = n - 1
	flag = True
	while low <= high and flag:
		if q[low] == q2:
			low += 1
		elif q[high] == q2:
			high -= 1
		else:
			if q[low] != q[high]:
				flag = False
			low += 1
			high -= 1
	if flag:
		print('YES')
		continue
	print('NO')


n = int(input())
for j in range(n):
	m = int(input())
	x = -1
	y = -1
	a = list(map(int, input().split()))
	for i in range(m // 2 + 1):
		if a[i] != a[m - 1 - i]:
			x = a[i]
			y = a[m - 1 - i]
			break
	if x == -1:
		print('YES')
		continue
	solved = False
	for num in [x, y]:
		t = []
		for i in a:
			if i != num:
				t.append(i)
		check = True
		for i in range(len(t) // 2 + 1):
			if t[i] != t[-i - 1]:
				check = False
				break
		if check:
			solved = True
			break
	if solved:
		print('YES')
	else:
		print('NO')


for j in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a1 = -1
	a2 = -1
	dis = n // 2
	if n % 2 == 1:
		dis += 1
	for i in range(dis):
		if arr[i] != arr[n - i - 1]:
			a1 = arr[n - i - 1]
			a2 = arr[i]
			break
	(crr, brr) = ([], [])
	for i in arr:
		if a1 != i:
			crr.append(i)
		if a2 != i:
			brr.append(i)
	if crr == crr[::-1] or brr == brr[::-1]:
		print('YES')
		continue
	print('NO')


import sys
from collections import deque
from collections import Counter
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	n = cin()
	arr = ari()
	ans = True

	def docheck(ele):
		nonlocal ans
		st = []
		for i in arr:
			if i != ele:
				st.append(i)
		if st == st[::-1]:
			ans = True
	for i in range(len(arr)):
		j = n - (i + 1)
		if arr[i] != arr[j]:
			value = arr[j]
			newval = arr[i]
			ans = False
			docheck(value)
			docheck(newval)
			break
	if ans:
		YES()
	else:
		NO()
	return
for _ in range(test_case):
	ans()


def check(arr, v, n):
	new = []
	for i in range(n):
		if arr[i] == v:
			continue
		new.append(arr[i])
	for j in range(len(new) // 2):
		if new[j] != new[len(new) - j - 1]:
			return False
	return True
for _ in range(int(input().strip())):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	ans = []
	for i in range(n // 2):
		if arr[i] != arr[n - i - 1]:
			ans.append(arr[i])
			ans.append(arr[n - i - 1])
			break
	if len(ans) == 0:
		print('YES')
		continue
	flag = 0
	for i in ans:
		ans = check(arr, i, n)
		if ans == True:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


def palindrome(arr, a):
	m = 0
	temp = []
	for i in arr:
		if i != a:
			temp.append(i)
			m += 1
	for i in range(m // 2):
		if temp[i] != temp[m - i - 1]:
			return False
	return True
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(a, b) = (0, 0)
	ans = True
	if n <= 2:
		print('YES')
	else:
		for i in range(n // 2):
			if arr[i] != arr[n - i - 1]:
				ans = False
				if palindrome(arr, arr[i]) or palindrome(arr, arr[n - i - 1]):
					print('YES')
				else:
					print('NO')
				break
		if ans:
			print('YES')


T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	j = len(arr) - 1
	if arr == arr[::-1]:
		print('YES')
		continue
	while arr[i] == arr[j]:
		i += 1
		j -= 1
	b = []
	for k in arr:
		if k == arr[i]:
			continue
		else:
			b.append(k)
	if b == b[::-1]:
		print('YES')
		continue
	b = []
	for k in arr:
		if k == arr[j]:
			continue
		else:
			b.append(k)
	if b == b[::-1]:
		print('YES')
		continue
	print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = True
	a = 0
	b = 0
	for i in range(n // 2):
		if l[i] != l[n - i - 1]:
			f = False
			a = l[i]
			b = l[n - i - 1]
			break
	if f:
		print('YES')
	else:
		ans1 = True
		i = 0
		j = n - i - 1
		while i <= j:
			if l[i] == l[j]:
				j -= 1
				i += 1
			elif l[i] != l[j] and l[i] == a:
				i += 1
			elif l[i] != l[j] and l[j] == a:
				j -= 1
			else:
				ans1 = False
				break
		ans2 = True
		i = 0
		j = n - i - 1
		while i <= j:
			if l[i] == l[j]:
				j -= 1
				i += 1
			elif l[i] != l[j] and l[i] == b:
				i += 1
			elif l[i] != l[j] and l[j] == b:
				j -= 1
			else:
				ans2 = False
				break
		if ans1 or ans2:
			print('YES')
		else:
			print('NO')


def res(arr, N):
	p1 = 0
	p2 = N - 1
	ind1 = ind2 = -1
	while p1 < p2:
		if arr[p1] != arr[p2]:
			ind1 = p1
			ind2 = p2
			break
		else:
			p1 += 1
			p2 -= 1
	else:
		print('YES')
		return
	l1 = [arr[ind1], arr[ind2]]
	for i in l1:
		stack = []
		for j in range(N):
			if arr[j] != i:
				stack.append(arr[j])
		p11 = 0
		p22 = len(stack) - 1
		while p11 < p22:
			if stack[p11] != stack[p22]:
				break
			else:
				p11 += 1
				p22 -= 1
		else:
			print('YES')
			return
	print('NO')
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	res(arr, N)