CF1660B.Vlad and Candies

Not so long ago, Vlad had a birthday, for which he was presented with a package of candies. There were $n$ types of candies, there are $a_i$ candies of the type $i$ ($1 \le i \le 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.

不久之前，弗拉德过生日，收到了一包糖果。共有 $n$ 种糖果，其中第 $i$ 种糖果有 $a_i$ 颗（$1 \le i \le n$）。

弗拉德决定每次只吃一颗糖果，并且每次都从当前数量最多的糖果类型中任选一种（若存在多个数量最多的类型，则可任选其一）。为了获得最大的进食愉悦感，弗拉德不希望连续两次吃到同一种类的糖果。

请帮助他判断：能否在不连续吃到相同种类糖果的前提下，将所有糖果全部吃完？

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) — the number of input test cases.

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

The first line of the case contains the single number $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of types of candies in the package.

The second line of the case contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the number of candies of the type $i$.

It is guaranteed that the sum of $n$ for all cases does not exceed $2 \cdot 10^5$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示输入测试用例的数量。

接下来是 $t$ 个测试用例的描述，每个测试用例占两行。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示该糖果包中糖果种类的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）—— 表示第 $i$ 种糖果的数量。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

Output $t$ 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).

输出 $t$ 行，每行包含对应输入测试用例的答案。若弗拉德能按计划吃糖果，则输出 "YES"；否则输出 "NO"。

答案的大小写不限（例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均被视为正确答案）。

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

• a candy of the type $2$, it is the most frequent, now $a = [2, 2]$;
• a candy of the type $1$, there are the same number of candies of the type $2$, but we just ate one, now $a = [1, 2]$;
• a candy of the type $2$, it is the most frequent, now $a = [1, 1]$;
• a candy of the type $1$, now $a = [0, 1]$;
• a candy of the type $2$, now $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 $2$ 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 $2$ again.

在第一个例子中，必须按以下顺序吃糖果：

• 一颗类型为 $2$ 的糖果（这是出现频率最高的类型），此时 $a = [2, 2]$；
• 一颗类型为 $1$ 的糖果（类型 $2$ 和类型 $1$ 当前数量相同，但我们刚刚吃掉了一颗类型 $2$ 的糖果），此时 $a = [1, 2]$；
• 一颗类型为 $2$ 的糖果（这是当前出现频率最高的类型），此时 $a = [1, 1]$；
• 一颗类型为 $1$ 的糖果，此时 $a = [0, 1]$；
• 一颗类型为 $2$ 的糖果，此时 $a = [0, 0]$，糖果已全部吃完。

在第二个例子中，所有糖果均为同一类型，因此无法在不连续吃两颗相同类型糖果的情况下吃完所有糖果。

在第三个例子中，首先将吃掉一颗类型为 $2$ 的糖果；此后，类型 $2$ 将成为唯一出现频率最高的类型，因此接下来仍不得不吃一颗类型为 $2$ 的糖果。