题目描述

不久前，光头强过生日，他收到了一袋糖果。这袋糖果包含了 $n$ 种糖果，其中第 $i(1≤i≤n)$ 种糖果有 $a_i$ 个。

光头强决定每次吃一颗糖果，选择当前最常见的糖果类型之中的任何一种（如果有多种类型的糖果同时是最常见的，则可以选择任何一种）。为了从吃糖果中获得最大的乐趣，光头强不想连续吃两颗相同类型的糖果。

帮助他判断他是否可以吃完所有的糖果而不连续吃两个相同类型的糖果。

输入格式

输入数据的第一行包含一个整数 $t(1≤t≤10^4)$ — 表示输入测试用例的数量。

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

每个测试用例的第一行包含单个数字 $n(1≤n≤2⋅10^5)$ — 表示这个糖果包里有多少种类型的糖果。

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

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

输出 $t$ 行，每行包含对应测试用例的答案。作为答案，输出 YES，如果光头强可以按计划吃糖果，否则输出 NO。

你可以任意输出大小写答案（例如，yEs，yes，Yes 和 YES 都会被认为是肯定的答案）。

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

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

一个类型为 2 的糖果，它是最常见的，现在 $a=[2,2]$ ；

一个类型为 1 的糖果，虽然 2 类型糖果也是最常见的，但我们刚刚吃掉了一个 2，现在 $a=[1,2]$ ；

一个类型为 2 的糖果，它是最常见的，现在 $a=[1,1]$ ；

一个类型为 1 的糖果，现在 $a=[0,1]$ ；

一个类型为 2 的糖果，现在 $a=[0,0]$ 。

然后糖果就被吃光了。

在第二个例子中，所有的糖果都是相同类型的，不可能不吃到两个相同类型的糖果。

在第三个例子中，首先吃掉一个类型为 2 的糖果，然后这种类型将保持最常见，你将不得不再吃一个类型为 2 的糖果。