链接：https://codeforces.ml/contest/1335/problem/E2

The only difference between easy and hard versions is constraints.

You are given a sequence aa consisting of nn positive integers.

Let's define a three blocks palindrome as the sequence, consisting of at most two distinct elements (let these elements are aa and bb, aa can be equal bb) and is as follows: [a,a,…,ax,b,b,…,by,a,a,…,ax][a,a,…,a⏟x,b,b,…,b⏟y,a,a,…,a⏟x]. There x,yx,y are integers greater than or equal to 00. For example, sequences [][], [2][2], [1,1][1,1], [1,2,1][1,2,1], [1,2,2,1][1,2,2,1] and [1,1,2,1,1][1,1,2,1,1] are three block palindromes but [1,2,3,2,1][1,2,3,2,1], [1,2,1,2,1][1,2,1,2,1] and [1,2][1,2] are not.

Your task is to choose the maximum by length subsequence of aa that is a three blocks palindrome.

You have to answer tt independent test cases.

Recall that the sequence tt is a a subsequence of the sequence ss if tt can be derived from ss by removing zero or more elements without changing the order of the remaining elements. For example, if s=[1,2,1,3,1,2,1]s=[1,2,1,3,1,2,1], then possible subsequences are: [1,1,1,1][1,1,1,1], [3][3] and [1,2,1,3,1,2,1][1,2,1,3,1,2,1], but not [3,2,3][3,2,3] and [1,1,1,1,2][1,1,1,1,2].

Input

The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt test cases follow.

The first line of the test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of aa. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2001≤ai≤200), where aiai is the ii-th element of aa. Note that the maximum value of aiai can be up to 200200.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).

Output

For each test case, print the answer — the maximum possible length of some subsequence of aa that is a three blocks palindrome.

Example

input

Copy

6
8
1 1 2 2 3 2 1 1
3
1 3 3
4
1 10 10 1
1
26
2
2 1
3
1 1 1

output

Copy

7
2
4
1
1
3

代码：

#include<bits/stdc++.h>
using namespace std;
int n,ans,t;
int m[205],b[205][200005]={0},dp[200005]={0},a[200005];
int main()
{
	cin>>t;
    while(t--)
    {
    	cin>>n;
		memset(m,0,sizeof(m));
		ans=0;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i];
			m[a[i]]++;
			b[a[i]][m[a[i]]]=i;
		}
		for(int i=1;i<=200;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(a[j]!=i)
				dp[j]=dp[j-1];
				else
				dp[j]=dp[j-1]+1;
			}
			for(int j=1;j<=200;j++)
			{
				ans=max(ans,m[j]);
				for(int k=1;2*k<=m[j];k++)
				{
					ans=max(ans,2*k+dp[b[j][m[j]-k+1]-1]-dp[b[j][k]]);
				}
			}
		}
		cout<<ans<<endl;
	}
}