题目内容

小 Q 有一个长度为 $n$ 的整数序列 $b_1, b_2, \dots, b_n$。他可以对该序列执行任意多次（包括 $0$ 次）如下操作：

选择一个下标 $i$（$1 \le i \le n$），并将 $b_i$ 替换为 $\left\lfloor \dfrac{b_i}{2} \right\rfloor$。

其中 $\lfloor x \rfloor$ 表示对 $x$ 向下取整。我们称一个长度为 $n$ 的序列是“完美的”，当且仅当它恰好包含 $1$ 到 $n$ 之间的每一个整数各一次。

小 Q 想知道，是否存在一个操作序列，使得最终得到的序列是一个完美序列？

约束：测试用例的数量 $T$ 不超过 $10^4$。每个序列的长度 $n$ 不超过 $2 \times 10^5$，且所有测试用例的 $n$ 之和也不超过 $2 \times 10^5$。序列中的每个元素均为不超过 $10^9$ 的非负整数。

输入描述

第一行包含一个整数 $T$，表示测试用例的数量。 接下来每两行描述一组测试用例：

• 第一行包含一个整数 $n$，表示序列的长度。
• 第二行包含 $n$ 个整数，由空格分隔，表示初始序列 $b_1, b_2, \dots, b_n$。

输出描述

对于每组测试用例，输出一行答案。如果可以经过操作使序列变为完美序列，输出 YES；否则输出 NO。输出的大小写形式可以任意选择。

样例1

输入

1
3
3 4 8

输出

YES

说明

序列为 [3, 4, 8]。

将数字从大到小处理：

• 8 执行两次除以 2 的操作：$8 \to 4 \to 2$，得到 2，在 $1$ 到 $3$ 范围内且未被占用，于是占用 2。
• 4 执行操作：$4 \to 2$（被占用）$\to 1$，得到 1 并占用。
• 3 原本就在范围内且未被占用，直接占用 3。

最终得到的数字集合为 {1, 2, 3}，可以构成完美序列，因此输出 YES。

样例2

输入

1
3
1 1 1

输出

NO

说明

序列为 [1, 1, 1]。

从大到小处理（均为 1）：

• 第一个 1 未被占用，直接占用 1。
• 第二个 1 发现 1 已被占用，执行除以 2 的操作：$\lfloor 1/2 \rfloor = 0$，变成 0。
• 第三个 1 同样变成 0。

由于 0 不能作为排列中的有效数字，无法得到 2 和 3，因此无法构成完美序列，输出 NO。

样例3

输入

1
1
5

输出

YES

说明

序列为 [5]。

$n=1$ 时的完美序列就是 [1]。 5 可以通过两次操作变为 1：$5 \to \lfloor 5/2 \rfloor = 2 \to \lfloor 2/2 \rfloor = 1$。 可以达成目标，因此输出 YES。

样例4

输入

1
1
0

输出

NO

说明

序列为 [0]。

$n=1$ 时的完美序列是 [1]，但 0 无论执行多少次除以 2 的操作都始终为 0：$\lfloor 0/2 \rfloor = 0$。 无法得到 1，因此输出 NO。