Підготовка до різдвяних свят

Вхідні дані

Кожен тест складається з декількох наборів вхідних даних. У першому рядку знаходиться одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^{4}), кількість наборів вхідних даних. Далі йде опис наборів вхідних даних.

Перший рядок містить одне ціле число $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5), кількість зібраних гілочок.

Другий рядок містить $n$ цілих чисел $w_{1}, w_{2}, \dots, w_{n}$ w_1, w_2, \ldots, w_n $(1 \leq w_{i} \leq 1 0^{9})$ (1 \le w_i \le 10^9), ваги відповідних гілочок.

Гарантується, що сума значень по $n$ за всіма наборами вхідних даних не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного набору вхідних даних виведіть "Yes", якщо можливо зібрати ялинку згідно традицій із заданих гілочок; в протилежному випадку виведіть "No".

Приклади

Приклад 1

Loading

Примітка

Для першого тестового випадку неможливо побудувати ялинку.

Для другого тестового випадку ми можемо побудувати ялинку наступним чином:

На верх ялинки ставимо гілочку вагою $1$ . Далі справа прикріпимо гілочку вагою $3$ , а зліва — вагою $4$ . Потім можемо справа прикріпити гілочку вагою $5$ та до неї гілочку вагою $2$ . Зліва прикріпимо гілочку вагою $6$ та до неї гілочку вагою $2$ .

Оцінювання

Підзадача $1$ ( $30$ балів): $(n \leq 20)$ (n \le 20)
Підзадача $2$ ( $40$ балів): $(n \leq 5 \cdot 1 0^{3})$ (n \le 5 \cdot 10^{3})
Підзадача $3$ ( $10$ балів): (усі ваги гілочок різні)
Підзадача $4$ ( $10$ балів): ( $c n t_{w_{i}} \leq 2$ cnt_{w_i} \le 2, де $c n t_{w_{i}}$ cnt_{w_i} — кількість гілочок вагою $w_{i}$ w_i)
Підзадача $5$ ( $60$ балів): ( $c n t_{ma x_v a l} = 2 \cdot k + 1$ cnt_{max\_val} = 2 \cdot k+1, де $c n t_{ma x_v a l}$ cnt_{max\_val} — кількість гілочок максимальної ваги)
Підзадача $6$ ( $150$ балів): Без додаткових обмежень