Preparation for the Christmas Holidays#12289
In the land of red foxes, Rudolandia, the winter holidays are approaching. Every year, on the eve of Christmas, they gather in the central forest glade to create the main festive Christmas tree of Rudolandia together. But this tree is unusual: they build it by hand from branches to make the tree as beautiful as possible.
The foxes have already collected branches, and each of them has a weight w_i. From these branches, they need to craft the perfect New Year's structure that will stand in the center of the glade and shine all winter. However, the ancient masters of Rudolandia left clear rules that must be followed, and the foxes need to understand whether it is possible to assemble the tree exactly as tradition requires.
Thus, while crafting the Christmas tree, the following rules must be adhered to:
All branches must be used.
To each branch, only one other branch can be attached, and the weight of the attached branch must be strictly less than the weight of the branch to which it is attached.
The structure of the tree must be strictly defined and symmetrical.
In Rudolandia, it is believed that a true Christmas tree must grow from a special trunk—a support in the center of the glade. Any number of branches can be attached to the trunk.
The tree must look as follows:
At the highest level (the top), there must be one branch—the main top.
At the next level—one branch on the right and one on the left.
At the next level—two branches on the right and two on the left.
And so on: at level , there must be branches on each side, that is, a total of 2 \cdot k.
Each test consists of several sets of input data. The first line contains one integer (1 \le t \le 10^{4}), the number of sets of input data. The following describes the sets of input data.
The first line contains one integer (1 \le n \le 2 \cdot 10^5), the number of collected branches.
The second line contains integers w_1, w_2, ..., w_n (1 \le w_i \le 10^9), the weights of the respective branches.
It is guaranteed that the sum of values of across all sets of input data does not exceed 2 \cdot 10^5.
For each set of input data, output "Yes" if it is possible to assemble the tree according to tradition from the given branches; otherwise, output "No".
Example 1
For the first test case, it is not possible to build the tree.
For the second test case, we can build the tree as follows:
At the top of the tree, we place a branch weighing 1. Then, we attach a branch weighing 3 on the right and a branch weighing 4 on the left. Next, we can attach a branch weighing 5 on the right and to it, a branch weighing 2. On the left, we will attach a branch weighing 6 and to it, a branch weighing 2.
Subtask ( points): (n \le 20)
Subtask ( points): (n \le 5 \cdot 10^{3})
Subtask ( points): (all branch weights are different)
Subtask ( points): (cnt_{w_i} \le 2, where cnt_{w_i} is the number of branches with weight w_i)
Subtask ( points): (cnt_{max\_val} = 2 \cdot k+1, where cnt_{max\_val} is the number of branches of maximum weight)
Subtask ( points): No additional constraints