C. Алиса и торт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы есть торт, и она собирается его разрезать. Она выполнит следующую операцию $$$n-1$$$ раз: выберет кусочек пирога (изначально весь торт является одним куском) с весом $$$w\ge 2$$$ и разрежем его на два более маленьких кусочка с весами $$$\lfloor\frac{w}{2}\rfloor$$$ и $$$\lceil\frac{w}{2}\rceil$$$ ($$$\lfloor x \rfloor$$$ и $$$\lceil x \rceil$$$ обозначают округление вниз и вверх, соответственно).

После того как Алиса разрежет торт на $$$n$$$ кусочков, она расположит эти $$$n$$$ кусочков на столе в произвольном порядке. Обозначим за $$$a_i$$$ вес $$$i$$$-го кусочка.

Вам дан массив $$$a$$$. Определите, существует ли некоторый начальный вес торта и последовательность операций разрезания такие, чтобы веса кусочков получались равными $$$a$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ для всех наборов входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку: выведите YES, если массив $$$a$$$ может быть получен с помощью действий Алисы, иначе выведите NO.

Вы можете выводить буквы в любом регистре (например, YES, Yes, yes, yEs будут приняты как положительный ответ).

Пример
Входные данные
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
Примечание

В первом примере можно получить массив $$$a$$$, выполнив $$$0$$$ операций с тортом веса $$$327$$$.

Во втором примере невозможно получить массив $$$a$$$.

В третьем примере можно получить массив $$$a$$$, выполнив $$$1$$$ операцию с тортом веса $$$1\,970\,429\,473$$$:

  • Разрезать торт пополам, веса будут равны $$$[985\,214\,736, 985\,214\,737]$$$.
Обратите внимание, что начальный вес торта может быть больше $$$10^9$$$.

В четвертом примере можно получить массив $$$a$$$ выполнив $$$2$$$ операции над тортом веса $$$6$$$:

  • Разрезать торт пополам, веса кусочков будут равны $$$[3,3]$$$.
  • Разрезать один из кусочков веса $$$3$$$, веса кусочков будут равны $$$[1, 2, 3]$$$, что совпадает с $$$[2, 3, 1]$$$ с точностью до порядка.