题目描述

这两个版本之间唯一的区别是，在这个版本中，数据范围较大。

最初，数组 $a$ 只包含数字 $1$。您可以执行多次操作来变化数组。每次操作，您可以选择 $a$ 的某个子数组，并将等于该子数组所有元素之和的元素添加到 $a$ 中。

换句话说，每次操作可以选择 $k(1≤k≤|a|)$ 个不同的索引 $i_1,i_2,…,i_k$，并将值等于 $a_{i_1}+a_{i_2}+…+a_{i_k}$ 的数字插入到新数组中。

给你一个目标数组 $c$。验证是否可以通过对初始数组执行一定量（可能为 $0$）的操作从初始数组 $a$ 变化到 $c$。

输入格式

输入的第一行包含一个整数 $t(1≤t≤1000)$ ——测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n(1≤n≤2×10^5)$，即最终数组 $c$ 应该具有的元素数。

每个测试用例的第二行包含 $n$ 个空间分隔的整数 $c_i(1≤c_i≤2×10^5)$ ——最终数组 $c$ 的元素，应该从初始数组 $a$ 中获得。

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

输出格式

对于每个测试用例，如果存在这样的操作数组，则输出YES，否则输出 NO。

输出无所谓大小写。

测试样例

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

YES
NO
YES
NO
YES
YES

样例说明

对于第一个测试用例，初始数组 $a$ 已经等于 $[1]$，所以答案是 YES。

对于第二个测试用例，初始数组为 $[1]$， 执行任何数量的操作都会将 $a$ 更改为大小至少为 $2$ 的数组，该数组不可能仅具有元素 $2$，即不可能获得数组 $[2]$，答案为 NO。

对于第三个测试用例，我们可以执行以下操作，以获得最终给定的数组c：

• 最初，$a=[1]$。
• 通过选择子数组 $[1]$，并在数组中插入 $1$，$a$ 将变为 $[1,1]$。
• 通过选择子数组 $[1,1]$，并在数组中间插入 $1+1=2$，将变为 $[1,2,1]$。
• 通过选择子数组 $[1,2]$，并在数组的第一个 $1$ 之后插入 $1+2=3$，$a$ 将变为 $[1,3,2,1]$。
• 通过选择子数组 $[1,3,1]$ 并在数组的开头插入 $1+3+1=5$，$a$ 将变为 $[5,1,3,2,1]$（这是我们需要获得的数组）。