两个版本之间的唯一区别是,在这个版本中,约束更高。
最初,数组 $$$a$$$ 仅包含数字 $$$1$$$。您可以执行多项操作来更改数组。在运算中,可以选择$$$a$$$的某个子序列$$$^{\dagger}$$$,并向$$$a$$$中添加一个等于该子序列所有元素之和的元素。
给你一个最终数组$$$c$$$。通过对初始数组执行一定数量(可能是 0)的操作,检查是否可以从初始数组 $$$a$$$ 获得 $$$c$$$。
$$$^{\dagger}$$$ 序列 $$$b$$$ 是序列 $$$a$$$ 的子序列,如果 $$$b$$$ 可以通过删除几个(可能为零,但不是全部)元素从 $$$a$$$ 获得。换句话说,选择 $$$k$$$ ($$$1 \leq k \leq |a|$$$) 不同索引 $$$i_1, i_2, \dots, i_k$$$ 并在 $$$a$$$ 中的任意位置插入一个新元素,其值等于 $$$a_{i_1} + a_{i_2} + \dots + a_{i_k}$$$。
输入
输入的第一行包含一个整数 $$$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”将被识别为肯定答案)。
示例
输入 #1
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
输出 #1
YES NO YES NO YES YES
注意
对于第一个测试用例,初始数组 $$$a$$$ 已经等于 $$$[1]$$$,所以答案是“YES”。
对于第二个测试用例,执行任意数量的操作都会将 $$$a$$$ 更改为大小至少为 2 的数组,并且不仅包含元素 $$$2$$$,因此不可能获得数组 $$$[2]$$$,答案是“NO”。
对于第三个测试用例,我们可以执行以下操作以获得最终给定的数组$$$c$$$:
- 最初,$$$a = [1]$$$。
- 通过选择子序列$$$[1]$$$,并在数组中插入$$$1$$$,$$$a$$$ 更改为$$$[1, 1]$$$。
- 通过选择子序列 $$$[1, 1]$$$,并在数组中间插入 $$$1+1=2$$$,$$$a$$$ 更改为 $$$[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]$$$ (这是我们需要获取的数组)。