You are given an array A of N positive integers. 

In one operation, you can do the following:
Choose integers i and j (1 ≤ i < j ≤ N), such that A_{i} = A_{j};
For all k (i < k < j), change the value of A_{k} to A_{i}.

Find out whether A can have at most 2 distinct values after using any (possibly zero) number of operations.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input:
- The first line of each test case contains N - the size of the array.
- The next line contains N integers, A_{1}, A_{2}, A_{3}, \ldots, A_{N} - the elements of the array.

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

For each test case, print YES if A can have at most 2 distinct values after using any (possibly zero) number of operations and NO otherwise. 

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

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
4
5
5 9 5 5 5
3
1 2 3
4
1 2 1 3
4
1 2 3 1

----- Sample Output 1 ------ 
YES
NO
YES
YES

----- explanation 1 ------ 
Test case $1$: The array $A$ already has $2$ distinct elements.

Test case $2$: It is impossible to make operations such that $A$ has $2$ distinct elements.

Test case $3$: We can make an operation as:
- Choose $i = 1$ and $j = 3$. Thus, we change $A_{2}$ to $A_{1} = 1$. 

The final array is $[1,1,1,3]$ which has two distinct elements.

Test case $4$: We can make an operation as:
- Choose $i = 1$ and $j = 4$. Thus, we change $A_{2}$ and $A_{3}$ to $A_{1} = 1$. 

The final array is $[1,1,1,1]$ which has one distinct element.

Difficulty: MEDIUM_HARD
Tags: Ad-hoc

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if len(set(arr)) <= 2 or arr[0] == arr[n - 1]:
		print('YES')
	else:
		flag = 0
		for i in range(1, n):
			if arr[i] == arr[n - 1] and arr[i - 1] == arr[0]:
				print('YES')
				flag = 1
				break
		if flag == 0:
			print('NO')


for i in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	if k[-1] == k[0] or k[-1] == k[1] or k[-2] == k[0]:
		print('YES')
		continue
	else:
		ff = 0
		for t in range(1, n - 1):
			if k[t] == k[0]:
				if k[t + 1] == k[-1]:
					ff = 1
					break
		if ff == 0:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split(' ')))
	start = A[0]
	end = A[-1]
	ex = 0
	if start == end:
		print('YES')
		ex = -1
	i = 0
	while i < N - 1 and ex == 0:
		if A[i] == start and A[i + 1] == end:
			print('YES')
			ex = 1
		i += 1
	if ex == 0:
		print('NO')


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	start = a[0]
	end = a[n - 1]
	back = n - 1
	distinct = False
	while back > -1:
		if start == a[back]:
			if back == n - 1:
				distinct = True
			elif a[back + 1] == end:
				distinct = True
			if distinct == True:
				break
		back -= 1
	if distinct == True:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	L = []
	L = [int(c) for c in input().split()]
	if L[0] == L[-1]:
		print('YES')
	else:
		for j in range(N):
			if [L[j - 1], L[j]] == [L[0], L[-1]]:
				print('YES')
				break
		else:
			print('NO')


t = int(input())
for I in range(t):
	n = int(input())
	n1 = [int(x) for x in input().split()]
	p = False
	if n1[0] == n1[n - 1]:
		p = True
	else:
		for i in range(n - 1):
			if n1[0] == n1[i] and n1[i + 1] == n1[-1]:
				p = True
	if p:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(f, l) = (a[0], a[n - 1])
	flag = 0
	if f == l:
		print('YES')
		continue
	for i in range(0, n - 1):
		if a[i] == f and a[i + 1] == l:
			flag = 1
			break
	print('YES') if flag == 1 else print('NO')


def Test(n, arr):
	if arr[0] == arr[-1]:
		return 'YES'
	else:
		for i in range(n - 1):
			if arr[0] == arr[i] and arr[i + 1] == arr[-1]:
				return 'YES'
		return 'NO'
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	print(Test(n, arr))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	if len(s) <= 2:
		print('YES')
	elif l[0] == l[-1] or l[0] == l[-2] or l[1] == l[-1]:
		print('YES')
	else:
		x = l[0]
		for i in range(1, n - 1):
			if l[i] == x and l[i + 1] == l[-1]:
				print('YES')
				break
		else:
			print('NO')


def main():
	t = int(input())
	for _ in range(t):
		numLen = int(input())
		nums = [int(x) for x in input().split()]
		isPresent = False
		if nums[0] == nums[numLen - 1]:
			isPresent = True
		else:
			for i in range(numLen - 1):
				if nums[0] == nums[i] and nums[i + 1] == nums[-1]:
					isPresent = True
		if isPresent:
			print('YES')
		else:
			print('NO')
main()


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	(l, r) = (nums[0], nums[-1])
	(ll, lr) = (0, n - 1)
	if l == r or n <= 2:
		print('YES')
	else:
		f = 0
		for (i, x) in enumerate(nums):
			if x == l:
				ll = i
			if x == r:
				lr = i
			if lr - ll == 1:
				f = 1
				break
		if f:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	flag = 'NO'
	if n <= 2 or a[0] == a[n - 1]:
		flag = 'YES'
	else:
		for i in range(n - 1):
			if a[i] == a[0] and a[i + 1] == a[n - 1]:
				flag = 'YES'
	print(flag)


def lsin():
	return list(map(int, input().split()))

def intin():
	return int(input())
for testcases in range(intin()):
	n = intin()
	a = lsin()
	flag = False
	if n <= 2 or a[0] == a[n - 1]:
		flag = True
	elif flag == False:
		for i in range(n - 1):
			if a[i] == a[0] and a[i + 1] == a[n - 1]:
				flag = True
	print('YES') if flag else print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n <= 2 or l[0] == l[-1]:
		print('YES')
	else:
		ans = 'NO'
		for i in range(n - 1):
			if l[0] == l[i] and l[i + 1] == l[-1]:
				ans = 'YES'
				break
		print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	ans = False
	ans = ans or a[0] == a[n - 1]
	for i in range(n - 1):
		ans = ans or (a[0] == a[i] and a[i + 1] == a[-1])
	if ans:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	k = False
	if array[0] == array[n - 1]:
		print('YES')
	else:
		for i in range(n - 1):
			if array[0] == array[i] and array[i + 1] == array[n - 1]:
				k = True
		if k:
			print('YES')
		else:
			print('NO')


def soln(n, arr):
	if n <= 2:
		return 'YES'
	if arr[0] == arr[-1] or arr[1] == arr[-1] or arr[0] == arr[-2]:
		return 'YES'
	cur = arr[0]
	for i in range(1, n - 1):
		if arr[i] == cur:
			if arr[i + 1] == arr[-1]:
				return 'YES'
	return 'NO'
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(soln(n, arr))


T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	if N <= 2:
		print('YES')
	elif L[0] == L[-1] or L[1] == L[-1] or L[0] == L[-2]:
		print('YES')
	else:
		x = L[0]
		for i in range(1, N - 1):
			if x == L[i] and L[i + 1] == L[-1]:
				print('YES')
				break
		else:
			print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr[0] == arr[-1]:
		ans = 'YES'
	else:
		for i in range(n - 1):
			if arr[i] == arr[0] and arr[i + 1] == arr[-1]:
				ans = 'YES'
				break
		else:
			ans = 'NO'
	print(ans)


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	ar = [int(x) for x in input().split()]
	status = False
	first = ar[0]
	last = ar[-1]
	if first == last:
		print('YES')
		continue
	for i in range(N - 1):
		if ar[i] == first and ar[i + 1] == last:
			status = True
			break
	if status:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n <= 2:
		print('YES')
	elif n == 3:
		if len(l) == len(set(l)):
			print('NO')
		else:
			print('YES')
	elif l[0] == l[-1] or l[0] == l[-2] or l[1] == l[-1]:
		print('YES')
	else:
		done = False
		for i in range(n):
			if l[i] == l[0] and l[i + 1] == l[-1]:
				print('YES')
				break
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	lst = [int(i) for i in input().split()]
	if lst[0] == lst[-1] or lst[0] == lst[n - 2] or lst[1] == lst[n - 1]:
		print('YES')
	elif n == 3:
		print('NO')
	else:
		flag = 0
		for i in range(1, n - 1):
			if lst[i] == lst[0] and lst[n - 1] == lst[i + 1]:
				flag = 1
				break
		if flag:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	temp = 0
	l1 = list((int(num) for num in input().strip().split()))[:n]
	if l1[0] == l1[-1]:
		print('YES')
	else:
		for j in range(n - 1):
			if l1[0] == l1[j] and l1[-1] == l1[j + 1]:
				temp = 1
				break
			else:
				pass
		if temp == 1:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	if l[0] == l[-1]:
		print('YES')
	else:
		c = 0
		for i in range(n - 1):
			if l[0] == l[i] and l[-1] == l[i + 1]:
				c = 1
				break
		if c == 1:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = 'NO'
	if a[0] == a[-1]:
		b = 'YES'
	else:
		for i in range(n - 1):
			if a[0] == a[i] and a[i + 1] == a[-1]:
				b = 'YES'
	print(b)


for _ in range(int(input())):
	n = int(input())
	array = [int(i) for i in input().split()]
	if array[0] == array[-1]:
		print('YES')
	else:
		flag = False
		for i in range(n - 1):
			if array[0] == array[i] and array[i + 1] == array[-1]:
				flag = True
				break
		if flag:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	a = 0
	b = 0
	if l[0] == l[len(l) - 1]:
		print('YES')
		a += 1
	if a == 0:
		for i in range(1, len(l)):
			if l[i] == l[len(l) - 1] and l[0] == l[i - 1] or (l[0] == l[len(l) - 1 - i] and l[len(l) - i] == l[len(l) - 1]):
				print('YES')
				b = +1
				break
	if a == 0 and b == 0:
		print('NO')


import sys
sys.setrecursionlimit(10 ** 9)
t = int(input())
for j in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l[0] == l[n - 1] or l[0] == l[n - 2] or l[1] == l[n - 1]:
		print('YES')
	else:
		p = False
		for i in range(1, n - 1):
			if l[0] == l[i] and l[i + 1] == l[n - 1]:
				p = True
				break
		if p:
			print('YES')
		else:
			print('NO')


import sys
import math
import bisect
import heapq
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from functools import cmp_to_key
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, stdin.readline().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, stdin.readline().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
sort = lambda x, compare: sorted(x, key=cmp_to_key(compare))
mod = 1000000007

def sumMod(a, b):
	return (a % mod + b % mod) % mod
for _ in range(stdint()):
	n = stdint()
	nums = seq()
	if n <= 2:
		print('YES')
	elif nums[0] == nums[n - 1]:
		print('YES')
	else:
		ans = 'NO'
		for i in range(n - 1):
			if nums[0] == nums[i] and nums[i + 1] == nums[n - 1]:
				ans = 'YES'
				break
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	c = 0
	(la, lb) = (len(a), len(b))
	if lb <= 2:
		print('YES')
	elif la == lb:
		print('NO')
	elif a[0] == a[-1]:
		print('YES')
	else:
		for i in range(la - 1):
			if a[i] == a[0] and a[i + 1] == a[la - 1]:
				c = c + 1
		if c == 0:
			print('NO')
		else:
			print('YES')


def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	arr = inparr()
	s1 = set(arr)
	if s1.__sizeof__() <= 2:
		print('YES')
	elif arr[0] == arr[N - 1]:
		print('YES')
	else:
		na = 1
		for i in range(N):
			if arr[i] == arr[0] and arr[i + 1] == arr[N - 1]:
				print('YES')
				na = 0
				break
		if na:
			print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = 'NO'
	if a[0] == a[-1]:
		p = 'YES'
	else:
		for i in range(n - 1):
			if a[i] == a[0] and a[i + 1] == a[-1]:
				p = 'YES'
	print(p)


def solve_testcase():
	n = int(input())
	arr = list(map(int, input().split()))
	if arr[0] == arr[-1]:
		return True
	for i in range(n - 1):
		if arr[i] == arr[0] and arr[i + 1] == arr[-1]:
			return True
	return False
for _ in range(int(input())):
	res = solve_testcase()
	if res:
		print('YES')
	else:
		print('NO')


test = int(input())
for z in range(test):
	n = int(input())
	A = list(map(int, input().split()))
	flag = False
	if A[0] == A[n - 1]:
		print('YES')
		continue
	for i in range(n - 1):
		if A[i] == A[0] and A[i + 1] == A[n - 1]:
			flag = True
			break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	counter = 0
	if l[0] == l[n - 1]:
		print('YES')
	else:
		for i in range(n - 1):
			if l[i] == l[0] and l[i + 1] == l[n - 1]:
				counter += 1
		if counter > 0:
			print('YES')
		else:
			print('NO')


for ___ in range(int(input())):
	mo = int(input())
	l3 = [int(x) for x in input().split()]
	if l3[0] == l3[-1]:
		print('YES')
	else:
		e = 0
		for i in range(len(l3) - 1):
			if l3[i] == l3[0] and l3[i + 1] == l3[-1]:
				e = 1
		if e == 1:
			print('YES')
		else:
			print('NO')


tescase = int(input())
while tescase:
	tescase -= 1
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == a[-1] or len(a) < 3:
		print('YES')
	else:
		flag = 0
		for i in range(len(a) - 1):
			if a[i] == a[0] and a[i + 1] == a[-1]:
				flag = 1
		if flag:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l[0] == l[-1] or n <= 2:
		print('YES')
	else:
		flag = 0
		for i in range(n - 1, -1, -1):
			if l[0] == l[i]:
				if l[i + 1] == l[-1]:
					print('YES')
					flag = 1
					break
		if flag == 0:
			print('NO')


for i in range(int(input())):
	n = int(input())
	a = [x for x in input().split()]
	if len(set(a)) <= 2 or a[0] == a[n - 1]:
		print('YES')
	else:
		for j in range(1, n):
			if a[0] == a[j - 1] and a[j] == a[n - 1]:
				print('YES')
				break
		else:
			print('NO')


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in sys.stdin.readline().split()]
	if a[0] == a[n - 1]:
		print('YES')
		continue
	else:
		flag = 0
		for i in range(n - 1):
			if a[i] == a[0] and a[i + 1] == a[n - 1]:
				flag = 1
		if flag:
			print('YES')
		else:
			print('NO')


def yash():
	n = int(input())
	lst = list(map(int, input().split()))
	if n <= 2:
		print('YES')
		return
	elif lst[0] == lst[n - 1] or lst[1] == lst[n - 1] or lst[0] == lst[n - 2]:
		print('YES')
		return
	else:
		a = lst[0]
		b = lst[n - 1]
		for i in range(n - 2):
			if lst[i] == a and lst[i + 1] == b:
				print('YES')
				return
		print('NO')
for _ in range(int(input())):
	yash()


t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == a[-1]:
		print('YES')
		continue
	flag = False
	for i in range(n - 1):
		if a[0] == a[i] and a[i + 1] == a[-1]:
			print('YES')
			flag = True
			break
	if not flag:
		print('NO')


listInput = lambda : list(map(int, input().split(' ')))
mapInput = lambda : map(int, input().split(' '))
for _ in range(int(input())):
	N = int(input())
	A = listInput()
	res = 'NO'
	if A[0] == A[-1]:
		res = 'YES'
	else:
		for i in range(N - 1):
			if A[0] == A[i] and A[i + 1] == A[-1]:
				res = 'YES'
				break
	print(res)