题目描述

给定一个序列 $[a_1,\ldots,a_n]$，其中每个元素 $a_i$ 只能是 $0$ 或 $1$。你可以对该序列进行若干次（也可以不进行）操作。每次操作，你可以选择两个整数 $1\le l\le r\le |a|$（其中 $|a|$ 表示当前序列 $a$ 的长度），并将 $[a_l,\ldots,a_r]$ 替换为一个元素 $x$，其中 $x$ 是 $[a_l,\ldots,a_r]$ 的“多数元素”。

这里，“多数元素”定义如下：假设该区间内有 $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 都视为肯定回答。

说明/提示

在样例的第四组测试数据中，初始序列为 $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]$。

由 ChatGPT 4.1 翻译

样例

5
1
0
1
1
2
01
9
100000001
9
000011000

No
Yes
No
Yes
No