序列 $$$a$$$ 通过网络发送,如下所示:
1. 序列$$$a$$$被分割成段(序列的每个元素恰好属于一个段,每个段是序列的一组连续元素);
2. 对于每个段,其长度写在它的旁边,可以是在它的左边,也可以是在它的右边;
3. 结果序列 $$$b$$$ 通过网络发送。
例如,我们需要发送序列 $$$a = [1, 2, 3, 1, 2, 3]$$$。假设它被分成如下段:$$$[\color{red}{1}] + [\color{blue}{2, 3, 1}] + [\color{green}{2, 3}]$$$。然后我们可以得到以下序列:
- $$$b = [1, \color{红色}{1}, 3, \color{蓝色}{2, 3, 1}, \color{绿色}{2, 3}, 2]$$$,
- $$$b = [\color{红色}{1}, 1, 3, \color{蓝色}{2, 3, 1}, 2, \color{绿色}{2, 3}]$$$,
- $$$b = [\color{红色}{1}, 1, \color{蓝色}{2, 3, 1}, 3, 2, \color{绿色}{2, 3}]$$$,
- $$$b = [\color{红色}{1}, 1,\color{蓝色}{2, 3, 1}, 3, \color{绿色}{2, 3}, 2]$$$。
如果使用了不同的分段,则发送的序列可能会有所不同。
给出了序列$$$b$$$。序列 $$$b$$$ 可以通过网络发送吗?换句话说,是否存在这样一个序列 $$$a$$$ ,将 $$$a$$$ 转换为通过网络发送它可能会导致序列 $$$b$$$ ?
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 序列 $$$b$$$ 的大小。
测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) - 序列 $$$b$$$ 本身。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上打印:
- 如果序列 $$$b$$$ 可以通过网络发送,即如果序列 $$$b$$$ 可以从某个序列 $$$a$$$ 获得并通过网络发送 $$$a$$$,则为 YES。
- 否则不。
在任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应)。
示例
输入 #1
7 9 1 1 2 3 1 3 2 2 3 5 12 1 2 7 5 6 5 7 8 9 10 3 4 4 8 6 2 2 3 1 10 4 6 2 1 9 4 9 3 4 2 1 1
输出 #1
YES YES YES NO YES YES NO
注意
在第一种情况下,序列 $$$b$$$ 可以从序列 $$$a = [1, 2, 3, 1, 2, 3]$$$ 中获得,并使用以下分区:$$$[\color{red}{1}] + [\color{blue}{2, 3, 1}] + [\color{green}{2, 3}]$$$。序列$$$b$$$:$$$[\color{red}{1}, 1, \color{blue}{2, 3, 1}, 3, 2, \color{green}{2, 3}]$$$。
在第二种情况下,序列 $$$b$$$ 可以从序列 $$$a = [12, 7, 5]$$$ 通过以下分区获得:$$$[\color{red}{12}] + [\color{green}{7, 5}]$$$。序列$$$b$$$:$$$[\color{red}{12}, 1, 2, \color{green}{7, 5}]$$$。
在第三种情况下,序列 $$$b$$$ 可以从序列 $$$a = [7, 8, 9, 10, 3]$$$ 中通过以下分区获得:$$$[\color{red}{7, 8, 9, 10, 3}]$$$。序列 $$$b$$$:$$$[5, \color{red}{7, 8, 9, 10, 3}]$$$。
在第四种情况下,不存在序列$$$a$$$,因此更改$$$a$$$通过网络传输可以产生序列$$$b$$$。