#P0036. 抢糖果

抢糖果

题目描述

小未和小来正在抢糖果。他们面前有一排 nn 个糖果袋,第 ii 个袋子里有 aia_i 粒糖果。他们两个将按照第一个袋子到第 nn 个袋子的顺序依次每轮拿取一个糖果袋。对于每个糖果袋的归属,他们有一个约定:如果一个袋子里的糖果数量是偶数,小未就抢走这袋糖果。否则则由小来拿去。

小未好胜心很强,所以他想重新排列这些糖果袋的顺序,这样在任何时刻(除了开始时两人都没有糖果),小未的糖果数都会严格多于小来。请帮助小未判断是否存在这样的重新排序可能。

输入格式

输入的第一行包含一个整数 tt ( 1≤t≤10001 \leq t \leq 1000 ) - 测试用例的数量。

每个测试用例的第一行包含一个整数 nn ( 1≤n≤1001 \leq n \leq 100 ) - 糖果袋的数量。

每个测试用例的第二行包含 nn 个空格分隔的整数 aia_i ( 1≤ai≤1001 \leq a_i \leq 100 ) - 每个袋子中糖果的数量。

输出格式

对于每个测试用例,如果存在重新排序使得任何时刻(除了开始时两人都没有糖果),小未的糖果数都会严格多于小来,则输出 YES,否则输出 NO。

样例 #1

样例输入 #1

3
4
1 2 3 4
4
1 1 1 2
3
1 4 3

样例输出 #1

YES
NO
NO

样例 11 解释

在第一个测试用例中,小未可以对数组进行如下重新排序: [4,1,2,3][4, 1, 2, 3] .然后过程如下

  • 第一个袋子中有 44 粒糖果,是偶数,所以小未拿走了它 - 小未有 44 粒糖果,小来有 00 粒糖果。
  • 第二个袋子里有 11 颗糖果,是奇数,所以被小来拿走了--小未有 44 颗糖果,小来有 11 颗。
  • 第三个袋子有 22 颗糖果,是偶数,所以小未拿走了它--小未有 66 颗糖果,而小来有 11 颗。
  • 第四袋有 33 颗糖果,是奇数,所以由小来拿走--小未有 66 颗糖果,小来有 44 颗糖果。

由于小未的糖果数量总是比小来多,所以这种重新排序是有效的。