群体狂乱

Problem Description

cats 正在玩炉石传说。现在，cats 的对手召唤了 $n$ 个随从，其中第 $i$ 个随从的攻击力和初始生命值均为 $a_i$。当两个随从互相攻击时，两个随从会同时扣除等同于对方随从攻击力的生命值，而它们的攻击力不会发生变化。当一个随从的生命值小于等于 $0$ 时，则认为这个随从死亡了。 为了消灭掉对手的这 $n$ 个随从，cats 打算使用一张卡：群体狂乱。这张卡的效果如下： 首先，随机生成一个长为 $n$ 的排列 $p_1,p_2,\dots p_n$，所有长为 $n$ 的排列均有可能被选择。然后，对于 $i = 1,2,\dots n$，依次执行：如果第 $p_i$ 个随从没有死亡，且至少存在一个其他随从没有死亡，则让第 $p_i$ 个随从与一个随机的没有死亡的其他随从互相攻击，每一个没有死亡的其他随从均有可能被选择。 现在，cats 想知道有没有可能通过使用一次群体狂乱消灭对手的全部 $n$ 个随从（即让 $n$ 个随从全部死亡）。你能帮 cats 算出答案吗？

Input

第一行包含一个整数 $T$ （$1\leq T \leq 5\cdot 10^4$），表示一共有 $T$ 组测试数据。 对于每组测试数据： 第一行为一个整数 $n$ （$1\leq n\leq 2\cdot 10^5$），表示对手召唤的随从总数。 第二行为 $n$ 个整数 $a_1,a_2,\dots a_n$ （$1\leq a_i \leq 10^9$），表示对手召唤的每个随从的攻击力和初始生命值。 保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^6$。

Output

对于每组测试数据，如果 cats 有可能通过使用一次群体狂乱消灭对手的全部 $n$ 个随从，输出 YES。否则，输出 NO。

Sample Input

8
3
2 3 2
3
1 3 1
4
9 9 9 9
3
7 7 7
5
8 5 8 4 8
6
9 7 7 7 7 7
6
9 8 7 7 7 7
5
8 9 1 8 8

Sample Output

YES
NO
YES
NO
YES
NO
YES
YES

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）