B. Vlad and Candies

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 aiai candies of the type ii (1≤i≤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≤t≤1041≤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≤n≤2⋅1051≤n≤2⋅105) — the number of types of candies in the package.

The second line of the case contains nn integers aiai (1≤ai≤1091≤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⋅1052⋅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).

Example

input

Copy

6
2
2 3
1
2
5
1 6 2 4 3
4
2 2 2 1
3
1 1000000000 999999999
1
1

output

Copy

YES
NO
NO
YES
YES
YES

Note

In the first example, it is necessary to eat sweets in this order:

• a candy of the type 22, it is the most frequent, now a=[2,2]a=[2,2];
• a candy of the type 11, there are the same number of candies of the type 22, but we just ate one, now a=[1,2]a=[1,2];
• a candy of the type 22, it is the most frequent, now a=[1,1]a=[1,1];
• a candy of the type 11, now a=[0,1]a=[0,1];
• a candy of the type 22, now a=[0,0]a=[0,0] and the candy has run out.

In the second example, all the candies are of the same type and it is impossible to eat them without eating two identical ones in a row.

In the third example, first of all, a candy of the type 22 will be eaten, after which this kind will remain the only kind that is the most frequent, and you will have to eat a candy of the type 22 again.

Problem solving instructions ： This problem is a simulation problem , Just judge that you don't take the same candy every time .

#include <stdio.h>

int main()
{
	int nCases;
	int n;
	int most, premost;
	int buf;
	scanf("%d", &nCases);
	while (nCases-- > 0) 
	{
		scanf("%d", &n);
		most = 0;
		premost = 0;
		while (n-- > 0)
		{
			scanf("%d", &buf);
			if (buf >= most) 
			{
				premost = most;
				most = buf;
			}
			else if (buf > premost)
			{
				premost = buf;
			}
		}
		if (most - premost <= 1)
		{
			puts("YES");
		}
		else
		{
			puts("NO");
		}
	}
	return 0;
}