不久前,弗拉德过了生日,他收到了一包糖果。有 $$$n$$$ 类型的糖果,有 $$$a_i$$$ 类型的糖果 $$$i$$$ ($$$1 \le i \le n$$$)。
Vlad决定每次只吃一颗糖果,选择当前最常吃的一种糖果(如果有多种这种类型,他可以选择其中任何一种)。为了获得最大的进食乐趣,弗拉德不想连续吃两颗同类型的糖果。
帮助他弄清楚他是否可以在不连续吃两颗相同糖果的情况下吃掉所有糖果。
输入
输入数据的第一行包含一个整数 $$$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$$$。
输出
输出 $$$t$$$ 行,每行包含输入对应测试用例的答案。作为答案,如果 Vlad 可以按计划吃糖果,则输出“YES”,否则输出“NO”。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #1
6 2 2 3 1 2 5 1 6 2 4 3 4 2 2 2 1 3 1 1000000000 999999999 1 1
输出 #1
YES NO NO YES YES YES
注意
在第一个例子中,需要按以下顺序吃甜食:
- $$$2$$$ 类型的糖果,它是最常见的,现在 $$$a = [2, 2]$$$;
- 一颗 $$$1$$$ 类型的糖果,有相同数量的 $$$2$$$ 类型的糖果,但我们只吃了一颗,现在 $$$a = [1, 2]$$$;
- $$$2$$$ 类型的糖果,它是最常见的,现在 $$$a = [1, 1]$$$;
- $$$1$$$ 类型的糖果,现在 $$$a = [0, 1]$$$;
- $$$2$$$ 类型的糖果,现在 $$$a = [0, 0]$$$ 并且糖果已经用完。
在第二个例子中,所有糖果都是同一类型,如果不连续吃掉两个相同的糖果就不可能吃掉它们。
在第三个例子中,首先会吃掉 $$$2$$$ 类型的糖果,之后这种糖果将成为唯一最常出现的糖果,然后你必须再次吃掉 $$$2$$$ 类型的糖果。