B. Сделать большинство
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность $$$[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]$$$.

Здесь большинство последовательности, состоящей из $$$0$$$ и $$$1$$$, определяется следующим образом: предположим, что в последовательности содержится $$$c_0$$$ нулей и $$$c_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 будут распознаны как положительные ответы.

Пример
Входные данные
5
1
0
1
1
2
01
9
100000001
9
000011000
Выходные данные
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]$$$.