题目描述

Elegy有一块蛋糕，他打算切开它。他将执行以下操作 n−1次：选择一块重量为w(w≥2)的蛋糕(最初，蛋糕都是一块)，然后将其切成重量为 ⌊w/2⌋ 和 ⌈w/2⌉的两小块(⌊x⌋ 和 ⌈x⌉ 分别表示向下取整和想上取整)。 把蛋糕切成n块后，他会把这些 n 块按照任意顺序排列在桌子上。设a[i]为排成一行的第 i 块的重量。 问是否存在原蛋糕，满足切法后构成该n块小蛋糕

输入格式

第一行包含一个整数 t(1≤t≤1e4) - 测试用例数。

每个测试用例的第一行包含一个整数 n(1≤n≤2e5)。

每个测试用例的第二行包含 n个整数 a1,a2,…,an( 1≤ai≤1e9)。

保证所有测试用例中 n的总和不超过 2e5。

输出格式

对于每个测试用例，打印一行：如果数组 a 是由 Elegy 的操作产生的，则打印 YES，否则打印 NO。

14
1
327
2
869 541
2
985214736 985214737
3
2 3 1
3
2 3 3
6
1 1 1 1 1 1
6
100 100 100 100 100 100
8
100 100 100 100 100 100 100 100
8
2 16 1 8 64 1 4 32
10
1 2 4 7 1 1 1 1 7 2
10
7 1 1 1 3 1 3 3 2 3
10
1 4 4 1 1 1 3 3 3 1
10
2 3 2 2 1 2 2 2 2 2
4
999999999 999999999 999999999 999999999

YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES

提示

在第一个测试用例中，可以通过对权重为 327 的蛋糕进行0次操作，得到数组 a。

在第二个测试用例中，无法得到数组 a。

在第三个测试用例中，通过对重量为 1970429473的蛋糕进行1次操作，可以得到数组 a： 将蛋糕切成两半，权重为 [985214736,985214737]。注意起始权重可以大于 1e9。

在第四个测试案例中，可以通过对权重为6的蛋糕进行2次操作，得到数组 a： 将蛋糕切成两半，权重为 [3,3]。将重量为 3的两块蛋糕中的一块切成两半，这样新的重量为 [1,2,3]，通过重新排列得到原数组a。