[C++知识库]C. 3SUM Closure

You are given an array?aa?of length?nn. The array is called?3SUM-closed?if for all distinct indices?ii,?jj,?kk, the sum?ai+aj+akai+aj+ak?is an element of the array. More formally,?aa?is 3SUM-closed if for all integers?1≤i<j<k≤n1≤i<j<k≤n, there exists some integer?1≤l≤n1≤l≤n?such that?ai+aj+ak=alai+aj+ak=al.

Determine if?aa?is 3SUM-closed.

Input

The first line contains an integer?tt?(1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains an integer?nn?(3≤n≤2?1053≤n≤2?105) — the length of the array.

The second line of each test case contains?nn?integers?a1,a2,…,ana1,a2,…,an?(?109≤ai≤109?109≤ai≤109) — the elements of the array.

It is guaranteed that the sum of?nn?across all test cases does not exceed?2?1052?105.

Output

For each test case, output "YES" (without quotes) if?aa?is 3SUM-closed and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Example

input

Copy

4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4

output

Copy

YES
NO
YES
NO

Note

In the first test case, there is only one triple where?i=1i=1,?j=2j=2,?k=3k=3. In this case,?a1+a2+a3=0a1+a2+a3=0, which is an element of the array (a2=0a2=0), so the array is 3SUM-closed.

In the second test case,?a1+a4+a5=?1a1+a4+a5=?1, which is not an element of the array. Therefore, the array is not 3SUM-closed.

In the third test case,?ai+aj+ak=0ai+aj+ak=0?for all distinct?ii,?jj,?kk, and?00?is an element of the array, so the array is 3SUM-closed.

思路：思考一下，当正数或者负数>=3的时候，一定不行，比如-1 -1 -2 4有三个正数，那么-1+-1+-2肯定越来越小，而最小就是-1，肯定不对，正数同理，所以正数和负数最多有两个，当正数有1个，负数有一个的话，剩下的肯定是0而且正数+负数==0才能符合题意，有两个负数一个正数，或者一个正数两个负数的话都是三个数加起来在数组里面有数才符合题意，所以当n==3的时候我们就直接判断三个数加起来有没有就行，那么如果有两个正数和两个负数的情况，肯定没有0，例如-1 -1 0 1 1，-1+-1肯定越来越小，再加一个0不变，所以得到的数比-1小的话不合题意，所以这种情况是n==4，当n==4的时候直接枚举看看是否满足即可，当n>4的时候，如果全是0的话，符合题意，如果只有一个不是0的话也符合题意。如果有两个不是0且这两个数加起来是0的话，也符合题意剩下的就都不符合题意。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
int n,k,x;
const int N=200005;
typedef long long ll;
ll a[N];
bool cheek(int a,int b,int c){
	if(a>=1&&a<=n&&b>=1&&b<=n&&c>=1&&c<=n)return true;
	else return false;
}
void sove(){
	cin>>n;
	map<int,int> mp;
	ll ans=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]++;
		ans+=a[i];
	}
	if(mp[0]==n||mp[0]==n-1){//全是0或者只有一个不是0的时候符合题意
		cout<<"YES"<<endl;
		return ;
	}
	if(n==3){//当等于3的时候需要判断加起来是不是出现过
		if(mp[ans]!=0){
			cout<<"YES"<<endl;
		}else cout<<"NO"<<endl;
		return ;
	}
	bool f=true;
	if(n==4){//等于4的时候枚举
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				for(int k=j+1;k<=n;k++){
					if(mp[a[i]+a[j]+a[k]]==0&&cheek(i,j,k))f=false;
				}
			}
		}
	if(f)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return ;
	}
	if(mp[0]!=n-2){
		cout<<"NO"<<endl;
	}else{
		if(mp[ans]!=0)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie() ,cout.tie() ;
	int t;
	cin>>t;
	while(t--){
		sove();
	}
	return 0;
}