#P1988B. Make Majority
Make Majority
Description
You are given a sequence where each element is either or . You can apply several (possibly zero) operations to the sequence. In each operation, you select two integers (where is the current length of ) and replace with a single element , where is the majority of .
Here, the majority of a sequence consisting of and is defined as follows: suppose there are zeros and ones in the sequence, respectively.
- If , the majority is .
- If , the majority is .
For example, suppose . If we select , the resulting sequence will be . If we select , the resulting sequence will be .
Determine if you can make with a finite number of operations.
Each test contains multiple test cases. The first line contains the number of test cases (). Description of the test cases follows.
The first line of each testcase contains one integer ().
The second line of each testcase contains a string consisting of and , describing the sequence .
It's guaranteed that the sum of over all testcases does not exceed .
For each testcase, if it's possible to make , print YES. Otherwise, print NO. You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.
Input
Each test contains multiple test cases. The first line contains the number of test cases (). Description of the test cases follows.
The first line of each testcase contains one integer ().
The second line of each testcase contains a string consisting of and , describing the sequence .
It's guaranteed that the sum of over all testcases does not exceed .
Output
For each testcase, if it's possible to make , print YES. Otherwise, print NO. You can output the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will be recognized as positive responses.
Note
In the fourth testcase of the example, initially . A valid sequence of operations is:
- Select and apply the operation. becomes .
- Select and apply the operation. becomes .