H - Vlad and Candies

Not so long ago, Vlad had a birthday, for which he was presented with a package of candies. There were nn types of candies, there are a_iai​ candies of the type ii (1 \le i \le n1≤i≤n).

Vlad decided to eat exactly one candy every time, choosing any of the candies of a type that is currently the most frequent (if there are several such types, he can choose any of them). To get the maximum pleasure from eating, Vlad does not want to eat two candies of the same type in a row.

Help him figure out if he can eat all the candies without eating two identical candies in a row.

Input

The first line of input data contains an integer tt (1 \le t \le 10^41≤t≤104) — the number of input test cases.

The following is a description of tt test cases of input, two lines for each.

The first line of the case contains the single number nn (1 \le n \le 2 \cdot 10^51≤n≤2⋅105) — the number of types of candies in the package.

The second line of the case contains nn integers a_iai​ (1 \le a_i \le 10^91≤ai​≤109) — the number of candies of the type ii.

It is guaranteed that the sum of nn for all cases does not exceed 2 \cdot 10^52⋅105.

Output

Output tt lines, each of which contains the answer to the corresponding test case of input. As an answer, output "YES" if Vlad can eat candy as planned, and "NO" otherwise.

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

Sample 1

Inputcopy	Outputcopy
6 2 2 3 1 2 5 1 6 2 4 3 4 2 2 2 1 3 1 1000000000 999999999 1 1	YES NO NO YES YES YES

题目大意：

给定一个序列，第 i 个位置代表第 i 种糖果的数量，每次吃糖果只能吃当前数量最多的糖果，并且每次相邻两次只能吃不同种类的糖果，问是否能够吃完所有糖果。

思路：考虑数量最多的糖果，第一次选择这种糖果，第二次就需要选择其它糖果，因此如果数量最多的这种糖果的数量比数量第二多的糖果的数量 + 1 还多，那么第二次只能吃数量最多的这种糖果，但又不能两次吃相同的糖果，因此一定吃不完所有糖果。反之一定能通过这两种糖果控制其它糖果的数量，从而吃掉所有糖果。

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main()
{
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		sort(a,a+n);
		if(a[n-1]-a[n-2]>1)
		cout<<"NO"<<endl;
		else
		cout<<"YES"<<endl;
	}
}