给定一个序列 $$$[a_1,\ldots,a_n]$$$,其中每个元素 $$$a_i$$$ 要么是 $$$0$$$ 要么是 $$$1$$$。您可以对序列应用多个(可能为零)操作。在每个操作中,您选择两个整数 $$$1\le l\le r\le |a|$$$(其中 $$$|a|$$$ 是 $$$a$$$ 的当前长度)并用单个元素 $$$x$$$ 替换 $$$[a_l,\ldots,a_r]$$$,其中 $$$x$$$ 是大多数$$$[a_l,\ldots,a_r]$$$。
这里,由 $$$0$$$ 和 $$$1$$$ 组成的序列的大部分定义如下:假设序列中分别有 $$$c_0$$$ 0 和 $$$c_1$$$ 1。
- 如果$$$c_0\ge c_1$$$,则大多数是$$$0$$$。
- 如果$$$c_0<c_1$$$,则大多数是$$$1$$$。
例如,假设 $$$a=[1,0,0,0,1,1]$$$。如果我们选择 $$$l=1,r=2$$$,则结果序列将为 $$$[0,0,0,1,1]$$$。如果我们选择 $$$l=4,r=6$$$,则结果序列将为 $$$[1,0,0,1]$$$。
确定是否可以通过有限次数的运算得到 $$$a=[1]$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 4\cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$)。
每个测试用例的第二行包含一个由 $$$0$$$ 和 $$$1$$$ 组成的字符串,描述序列 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果可以使 $$$a=[1]$$$,则打印 YES。否则,打印NO。您可以在任何情况下输出答案(上限或下限)。例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应。
示例
输入 #1
5 1 0 1 1 2 01 9 100000001 9 000011000
输出 #1
No Yes No Yes No
注意
在示例的第四个测试用例中,最初 $$$a=[1,0,0,0,0,0,0,0,1]$$$。有效的操作顺序是:
1. 选择 $$$l=2,r=8$$$ 并应用操作。 $$$a$$$ 变为 $$$[1,0,1]$$$。
2. 选择$$$l=1,r=3$$$ 并应用该操作。 $$$a$$$ 变为 $$$[1]$$$。