CF1919D.01 Tree

There is an edge-weighted full binary tree with $n$ leaves. A full binary tree is defined as a tree where every non-leaf vertex has exactly 2 children. For each non-leaf vertex, we label one of its children as the left child and the other as the right child.

The binary tree has a very strange property. For every non-leaf vertex, one of the edges to its children has weight $0$ while the other edge has weight $1$. Note that the edge with weight $0$ can be connected to either its left or right child.

You forgot what the tree looks like, but luckily, you still remember some information about the leaves in the form of an array $a$ of size $n$. For each $i$ from $1$ to $n$, $a_i$ represents the distance$^\dagger$ from the root to the $i$-th leaf in dfs order$^\ddagger$. Determine whether there exists a full binary tree which satisfies array $a$. Note that you do not need to reconstruct the tree.

$^\dagger$ The distance from vertex $u$ to vertex $v$ is defined as the sum of weights of the edges on the path from vertex $u$ to vertex $v$.

$^\ddagger$ The dfs order of the leaves is found by calling the following $\texttt{dfs}$ function on the root of the binary tree.

dfs_order = []

function dfs(v):
if v is leaf:
append v to the back of dfs_order
else:
dfs(left child of v)
dfs(right child of v)

dfs(root)

存在一棵带边权的满二叉树，其含有 $n$ 个叶子节点。满二叉树定义为：每个非叶子节点恰好有两个子节点。对每个非叶子节点，我们将其两个子节点分别标记为左子节点和右子节点。

该二叉树具有一个非常特殊的性质：对每个非叶子节点，连接它与其两个子节点的两条边中，一条边的权重为 $0$，另一条边的权重为 $1$。注意：权重为 $0$ 的边可以连接到左子节点或右子节点中的任意一个。

你已忘记了该树的具体结构，但幸运的是，你还记得关于叶子节点的部分信息，这些信息以一个长度为 $n$ 的数组 $a$ 的形式保存。对每个从 $1$ 到 $n$ 的 $i$，$a_i$ 表示在 DFS 序$^\ddagger$中第 $i$ 个叶子节点到根节点的距离$^\dagger$。请判断是否存在一棵满足数组 $a$ 的满二叉树。注意：你无需重构该树。

$^\dagger$ 顶点 $u$ 到顶点 $v$ 的距离定义为从 $u$ 到 $v$ 的路径上所有边的权重之和。

$^\ddagger$ 叶子节点的 DFS 序通过在二叉树根节点上调用如下 $\texttt{dfs}$ 函数得到：

dfs_order = []

function dfs(v):
if v is leaf:
append v to the back of dfs_order
else:
dfs(left child of v)
dfs(right child of v)

dfs(root)

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2\cdot 10^5$) — the size of array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le n - 1$) — the distance from the root to the $i$-th leaf.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2\cdot 10^5$），表示数组 $a$ 的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le n - 1$），其中 $a_i$ 表示从根节点到第 $i$ 个叶子节点的距离。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case, print "YES" if there exists a full binary tree which satisfies array $a$ and "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as a positive answer).

对于每个测试用例，如果存在一棵满足数组 $a$ 的满二叉树，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出每个字母（例如，"YES"、"Yes"、"yes"、"yEs" 均被视为正确答案）。

In the first test case, the following tree satisfies the array.

In the second test case, it can be proven that there is no full binary tree that satisfies the array.

在第一个测试用例中，以下树满足该数组。

在第二个测试用例中，可以证明不存在满足该数组的满二叉树。