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 ai=an−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≤t≤100) — the number of test cases.
Next 2t lines describe test cases. The first line of the test case contains one integer n (3≤n≤5000) — the length of a. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤n), where ai is the i-th element of a.
It is guaranteed that the sum of n over all test cases does not exceed 5000 (∑n≤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.
题目大意：多组测试样例。对于每组测试样例，输入n，然后输入n个数，可以删除这个数组中任意元素，判断这个数组是不是回文数组，（回文数组可以是【1，2，1】，【1，2，3，2，1】）。
解题思路：因为n是大于等于三的，我们输入的时候判断一下，如果n小于3直接出no就可以了，我们可以以1到n-1中的数作分割，然后判断 i 前面的数和 i 后面的数是否有重合，如果重合则说明一定是个回文数组，我们设一个标记数组，再设一个flag判断是否为回文数组，每次都将 i 之前的数全部置为true，后面如果遇到了true则将flag置为yes并退出循环，最后根据flag的值来确定是不是一个回文数组。AC代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=5e3+50;
int a[N];
bool book[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n<3)
{
cout<<"NO"<<endl;
continue;
}
memset(book,false,sizeof book);
for(int i=0;i<n;i++)
cin>>a[i];
bool flag=false;
for(int i=1;i<n;i++)//以第i个数为分割
{
for(int j=0;j<i;j++)//标记i前面的数
book[a[j]]=true;
for(int j=i+1;j<n;j++)//判断i后面的数
if(book[a[j]])
{
flag=true;
break;
}
if(flag)
break;
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
//system("pause");
return 0;
}