310271: CF1807G2. Subsequence Addition (Hard Version)

G2. Subsequence Addition (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The only difference between the two versions is that in this version, the constraints are higher.

Initially, array $a$ contains just the number $1$. You can perform several operations in order to change the array. In an operation, you can select some subsequence$^{\dagger}$ of $a$ and add into $a$ an element equal to the sum of all elements of the subsequence.

You are given a final array $c$. Check if $c$ can be obtained from the initial array $a$ by performing some number (possibly 0) of operations on the initial array.

$^{\dagger}$ A sequence $b$ is a subsequence of a sequence $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly zero, but not all) elements. In other words, select $k$ ($1 \leq k \leq |a|$) distinct indices $i_1, i_2, \dots, i_k$ and insert anywhere into $a$ a new element with the value equal to $a_{i_1} + a_{i_2} + \dots + a_{i_k}$.

Input

The first line of the input contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$)  — the number of elements the final array $c$ should have.

The second line of each test case contains $n$ space-separated integers $c_i$ ($1 \leq c_i \leq 2 \cdot 10^5$)  — the elements of the final array $c$ that should be obtained from the initial array $a$.

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

Output

For each test case, output "YES" (without quotes) if such a sequence of operations exists, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

ExampleInput

6
1
1
1
2
5
5 1 3 2 1
5
7 1 5 2 1
3
1 1 1
5
1 1 4 2 1

Output

YES
NO
YES
NO
YES
YES

Note

For the first test case, the initial array $a$ is already equal to $[1]$, so the answer is "YES".

For the second test case, performing any amount of operations will change $a$ to an array of size at least two which doesn't only have the element $2$, thus obtaining the array $[2]$ is impossible and the answer is "NO".

For the third test case, we can perform the following operations in order to obtain the final given array $c$:

• Initially, $a = [1]$.
• By choosing the subsequence $[1]$, and inserting $1$ in the array, $a$ changes to $[1, 1]$.
• By choosing the subsequence $[1, 1]$, and inserting $1+1=2$ in the middle of the array, $a$ changes to $[1, 2, 1]$.
• By choosing the subsequence $[1, 2]$, and inserting $1+2=3$ after the first $1$ of the array, $a$ changes to $[1, 3, 2, 1]$.
• By choosing the subsequence $[1, 3, 1]$ and inserting $1+3+1=5$ at the beginning of the array, $a$ changes to $[5, 1, 3, 2, 1]$ (which is the array we needed to obtain).

题目大意：

这个题目是“子序列加法”的困难版本，与简单版本唯一的不同在于这个版本的限制条件更高。

最初，数组 $ a $ 只包含数字 $ 1 $。你可以执行几个操作来改变数组。在一次操作中，你可以选择 $ a $ 的某个子序列，并向 $ a $ 中添加一个等于子序列所有元素和的新元素。

给你一个最终数组 $ c $。检查是否可以通过对初始数组 $ a $ 执行若干次（可能为 0 次）操作来从初始数组得到数组 $ c $。

输入输出数据格式：

输入：

第一行包含一个整数 $ t $（$ 1 \leq t \leq 1000 $），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $），表示最终数组 $ c $ 应该有的元素数量。

每个测试用例的第二行包含 $ n $ 个空格分隔的整数 $ c_i $（$ 1 \leq c_i \leq 2 \cdot 10^5 $），表示应该从初始数组 $ a $ 得到的最终数组 $ c $ 的元素。

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

输出：

对于每个测试用例，如果存在这样的操作序列，输出 "YES"（不包含引号），否则输出 "NO"（不包含引号）。

你可以以任何大小写形式输出答案，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的回答。题目大意： 这个题目是“子序列加法”的困难版本，与简单版本唯一的不同在于这个版本的限制条件更高。 最初，数组 $ a $ 只包含数字 $ 1 $。你可以执行几个操作来改变数组。在一次操作中，你可以选择 $ a $ 的某个子序列，并向 $ a $ 中添加一个等于子序列所有元素和的新元素。 给你一个最终数组 $ c $。检查是否可以通过对初始数组 $ a $ 执行若干次（可能为 0 次）操作来从初始数组得到数组 $ c $。 输入输出数据格式： 输入： 第一行包含一个整数 $ t $（$ 1 \leq t \leq 1000 $），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 2 \cdot 10^5 $），表示最终数组 $ c $ 应该有的元素数量。 每个测试用例的第二行包含 $ n $ 个空格分隔的整数 $ c_i $（$ 1 \leq c_i \leq 2 \cdot 10^5 $），表示应该从初始数组 $ a $ 得到的最终数组 $ c $ 的元素。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 输出： 对于每个测试用例，如果存在这样的操作序列，输出 "YES"（不包含引号），否则输出 "NO"（不包含引号）。 你可以以任何大小写形式输出答案，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的回答。