You are given an array $a$ consisting of $n$ integers.

Your task is to determine if $a$ has some subsequence of length at least $3$ that is a palindrome.

Recall that an array $b$ is called a subsequence of the array $a$ if $b$ can be obtained by removing some (possibly, zero) elements from $a$ (not necessarily consecutive) without changing the order of remaining elements. For example, $[2]$, $[1, 2, 1, 3]$ and $[2, 3]$ are subsequences of $[1, 2, 1, 3]$, but $[1, 1, 2]$ and $[4]$ are not.

Also, recall that a palindrome is an array that reads the same backward as forward. In other words, the array $a$ of length $n$ is the palindrome if $a_i = a_{n - i - 1}$ for all $i$ from $1$ to $n$. For example, arrays $[1234]$, $[1, 2, 1]$, $[1, 3, 2, 2, 3, 1]$ and $[10, 100, 10]$ are palindromes, but arrays $[1, 2]$ and $[1, 2, 3, 1]$ are not.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

Next $2t$ lines describe test cases. The first line of the test case contains one integer $n$ ($3 \le n \le 5000$) — the length of $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$ ($\sum n \le 5000$).


-----Output-----

For each test case, print the answer — "YES" (without quotes) if $a$ has some subsequence of length at least $3$ that is a palindrome and "NO" otherwise.


-----Example-----
Input
5
3
1 2 1
5
1 2 2 3 2
3
1 1 2
4
1 2 2 1
10
1 1 2 2 3 3 4 4 5 5

Output
YES
YES
NO
YES
NO



-----Note-----

In the first test case of the example, the array $a$ has a subsequence $[1, 2, 1]$ which is a palindrome.

In the second test case of the example, the array $a$ has two subsequences of length $3$ which are palindromes: $[2, 3, 2]$ and $[2, 2, 2]$.

In the third test case of the example, the array $a$ has no subsequences of length at least $3$ which are palindromes.

In the fourth test case of the example, the array $a$ has one subsequence of length $4$ which is a palindrome: $[1, 2, 2, 1]$ (and has two subsequences of length $3$ which are palindromes: both are $[1, 2, 1]$).

In the fifth test case of the example, the array $a$ has no subsequences of length at least $3$ which are palindromes.

Difficulty: introductory

Starter code:

Solutions:
for i in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    flag = False
    for j in range(len(arr)):
        for c in range(j + 2, len(arr)):
            if arr[c] == arr[j]:
                flag = True
                break
    print("YES" if flag else "NO")


q = int(input())
for rwe in range(q):
	n = int(input())
	l = list(map(int,input().split()))
	dasie = False
	d = {}
	for i in range(n):
		d[l[i]] = []
	for i in range(n):
		d[l[i]].append(i)
	for elt in d:
		if len(d[elt]) > 2:
			dasie = True
			break
		if len(d[elt]) < 2:
			continue
		if len(d[elt]) == 2:
			if d[elt][0] != d[elt][1] - 1:
				dasie = True
	if dasie:
		print("YES")
	else:
		print("NO")

from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

for _ in range(val()):
    n = val()
    l = li()
    d = {}
    ans = 'NO'
    for i in range(n):
        if l[i] in d:
            if i - d[l[i]]> 1:
                ans = 'YES'
                break
        else:
            d[l[i]] = i
    print(ans)

from sys import stdin,stdout                           #
import math                                            #
import heapq                                           #
                                                       #
t = 1                                                  #
def aint():                                            #
	return int(input().strip())                        #
def lint():                                            #
	return list(map(int,input().split()))              #
def fint():                                            #
	return list(map(int,stdin.readline().split()))     #
                                                       #	
########################################################

def main():
	n=aint()
	l=lint()
	ans="NO"
	for i in range(n):
		for j in range(i+2,n):
			if l[i]==l[j]:
				ans="YES"
				break
	print(ans)
	#solve

t=int(input())

########################################################
for i in range(t):                                     #
	main()                                             #


t = int(input())

for loop in range(t):

    n = int(input())

    a = list(map(int,input().split()))

    lis = [None] * (n+1)

    ans = "NO"
    for i in range(n):

        if lis[a[i]] == None:
            lis[a[i]] = i
        elif lis[a[i]] + 1 < i:
            ans = "YES"
            break

    print (ans)


#!/usr/bin/env python3
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(item) for item in input().split()]
    ok = False
    for i in range(n-2):
        for j in range(i+2, n):
            if a[i] == a[j]:
                ok = True
    if ok:
        print("YES")
    else:
        print("NO")

def main():
    import sys
    input = sys.stdin.readline

    for _ in range(int(input())):
        N = int(input())
        A = list(map(int, input().split()))
        dic = {}
        ok = 0
        for i, a in enumerate(A):
            if a not in dic:
                dic[a] = i
            else:
                if i - dic[a] > 1:
                    ok = 1
                    break
        if ok:
            print('YES')
        else:
            print('NO')


def __starting_point():
    main()

__starting_point()

import sys
import math
import bisect

def solve(A):
    n = len(A)
    d = dict()
    for i in range(n):
        if A[i] not in d:
            d[A[i]] = i
        else:
            if i - d[A[i]] > 1:
                return True
    return False

def main():
    for _ in range(int(input())):
        n = int(input())
        A = list(map(int, input().split()))
        if solve(A):
            print('YES')
        else:
            print('NO')

def __starting_point():
    main()

__starting_point()

t = int(input())
while(t):
    t -= 1
    n = int(input())
    a = list(map(int, input().split()))
    d = dict()
    for i in range(n):
        if(a[i] in d):
            d[a[i]].append(i)
        else:
            d[a[i]] = [i]
    flag = 1
    for i in d:
        if(len(d[i]) >= 3):
            print("YES")
            break
    else:
        for i in d:
            if(len(d[i]) >= 2 and d[i][-1] - d[i][0] >= 2):
                print("YES")
                break
        else:
            print("NO")

t = int(input())
for i in range(t):
    n = int(input())
    data = tuple(map(int, input().split()))
    met = []
    for i in data:
        if i in met[:-1]:
            print("YES")
            break
        met.append(i)
    else:
        print("NO")
    


t = int(input())
for i in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    cnt = [[] for i in range(n + 2)]
    for i in range(n):
        cnt[arr[i]].append(i)
    for el in cnt:
        if len(el) > 2:
            print("YES")
            break
        if (len(el) < 2):
            continue
        if abs(el[1] - el[0]) != 1:
            print("YES")
            break
    else:
        print("NO")


def go():
    n = int(input())
    a = list(map(int, input().split()))
    d = {}
    for i, aa in enumerate(a):
        if aa in d:
            if i - d[aa] > 1 :
                return 'YES'
        d[aa] = d.get(aa, i)
    return 'NO'


t = int(input())
for _ in range(t):
    print(go())


def f(N,L):
    V=[0]*(N+1)
    for i,a in enumerate(L):
        if V[a]>0:
            r=V[a]
            if L[i-1]==a:
                r-=1
            if r>0:
                return True
        V[a]+=1
    return False

for _ in range(int(input())):
    N=int(input())
    L=list(map(int,input().split()))
    if f(N,L): print('YES')
    else: print('NO')

import sys
input = sys.stdin.readline

Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    A = list(map(int, input().split()))
    Query.append((N, A))

for N, A in Query:
    dic = {}
    for i, a in enumerate(A):
        if not a in dic:
            dic[a] = [i]
        else:
            dic[a].append(i)
    
    ok = False
    for L in dic.values():
        if len(L) > 1 and L[-1] - L[0] > 1:
            ok = True
            break
    print("YES" if ok else "NO")

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    i1 = 0
    i2 = n
    flag = False
    for i in range(n-2):
        e1 = a[i]
        for j in range(i+2, n):
            if e1 == a[j]:
                print('YES')
                flag = True
                break
        if flag == True:
            break
    if flag == False:
        print('NO')

for i in range(int(input())):
    solve()

t=int(input())
for x in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    b={}
    for x in range(n):
        if a[x] in b:
            if b[a[x]][-1]!=x-1:
                b[a[x]].append(x)
        else:b[a[x]]=[x]
    t=False
    for x in b:
        if len(b[x])>=2:
            t=True
    if t:
        print('YES')
    else:
        print('NO')


import sys

input = sys.stdin.readline

q = int(input())

for _ in range(q):
    N = int(input())
    A = list(map(int, input().split()))
    if N < 3:
        print("NO")
    else:
        ans = False
        for i in range(N - 2):
            x = A[i]
            for j in range(i + 2, N):
                if A[j] == x:
                    ans = True
        if ans:
            print("YES")
        else:
            print("NO")

import math
 
 
class Read:
    @staticmethod
    def string():
        return input()
 
    @staticmethod
    def int():
        return int(input())
 
    @staticmethod
    def list(sep=' '):
        return input().split(sep)
 
    @staticmethod
    def list_int(sep=' '):
        return list(map(int, input().split(sep)))
 
result = math.inf
 
def solve():
  n = Read.int()
  a = Read.list_int();
  for i in range(n):
    for j in range(i + 2, n):
      if a[i] == a[j]:
        print('YES')
        return
  print('NO')
 
# query_count = 1
query_count = Read.int()
while query_count:
    query_count -= 1
    solve()

import sys

for _ in range(int(sys.stdin.readline().rstrip())):
    n = int(sys.stdin.readline().rstrip())
    num = list(map(int, sys.stdin.readline().rstrip().split()))
    re = False
    for i in range(len(num)):
        for j in range(i + 2, len(num)):
            if num[i] == num[j]:
                re = True
                break
        if re:
            break
    if re:
        print('YES')
    else:
        print('NO')


def solve(n, a):
    d = {}
    for i, aa in enumerate(a):
        if aa in d:
            d[aa].append(i)
        else:
            d[aa] = [i]
    for k in d:
        if len(d[k]) > 2:
            return "YES"
        if len(d[k]) == 2:
            if d[k][1] - d[k][0] > 1:
                return "YES"
    return "NO"


def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = [int(i) for i in input().split()]
        print(solve(n, a))


main()


def solve():
  n=int(input())
  a=list(map(int,input().split()))
  ans="NO"
  d={}
  for i in range(n):
    if a[i] not in d:d[a[i]]=i
    elif i-1>d[a[i]]:ans="YES"
  return ans
for _ in range(int(input())):
  print(solve())