CF2242B.Predominant Frequency Division

You are given an array $a$ consisting of the numbers $1$, $2$, and $3$. Check whether it is possible to split it into three contiguous non-empty parts such that, for each part $i$ from $1$ to $3$, the following condition holds:

• the number of elements greater than $i$ is at most half of the part.

In other words, you need to divide the array $a$ into three pairwise disjoint contiguous non-empty parts so that in the left part the number of ones is at least the total number of twos and threes, in the middle part the total number of ones and twos is at least the number of threes, and the right part can be anything, but it must be non-empty.

For example, the array $[2, 1, 1, 3, 3, 1, 2, 3]$ can be split into three parts: $[2, 1, 1, 3]$, $[3, 1, 2]$, and $[3]$. And the array $[2, 1, 3, 3, 3, 2, 3]$ cannot be split in such a way.

给你一个由数字 $1$、$2$ 和 $3$ 组成的数组 $a$。请判断是否可以将其划分为三个连续的、非空的部分，使得对每个从 $1$ 到 $3$ 的部分 $i$，以下条件均成立：

• 该部分中大于 $i$ 的元素个数至多为该部分长度的一半。

换言之，你需要将数组 $a$ 划分为三个两两不相交、连续且非空的部分，使得：

• 在左部分中，$1$ 的个数不少于 $2$ 与 $3$ 的总个数；
• 在中部分中，$1$ 与 $2$ 的总个数不少于 $3$ 的个数；
• 右部分可以任意（无额外限制），但必须非空。

例如，数组 $[2, 1, 1, 3, 3, 1, 2, 3]$ 可划分为三部分：$[2, 1, 1, 3]$、$[3, 1, 2]$ 和 $[3]$；而数组 $[2, 1, 3, 3, 3, 2, 3]$ 则无法按此方式划分。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($3 \le n \le 2 \cdot 10^{5}$) — the length of the array.

The second line of each test case contains $n$ integers $a_{i}$ ($1 \le a_{i} \le 3$).

Additional constraints on the input data:

• the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^{5}$）—— 表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_{i}$（$1 \le a_{i} \le 3$）。

输入数据的额外约束：

• 所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^{5}$。

For each test case, print YES if there exists a way to split the array as required, and NO otherwise.

You may print the answer in any case. For example, YeS, YES, NO, nO will also be accepted.

对于每个测试用例，如果存在一种符合要求的数组划分方式，则输出 YES；否则输出 NO。

您可以以任意大小写形式输出答案。例如，YeS、YES、NO、nO 均可被接受。

The first two test cases are explained in the statement.

In the third test case, the left part may be $[1]$, but then any choice of the middle part ($[3]$, $[3, 3]$, $[3, 3, 2]$) does not work. The left part may also be $[1, 3]$; then the middle part must be $[3, 2]$, and in this case the right part is empty. Therefore, the answer for the third example is NO.

In the fourth test case, the only valid left part is the entire array, because on any non-empty shorter prefix the number of ones is less than the number of twos, so the middle and right parts cannot both be non-empty.

In the fifth test case, the split $[3, 2, 1, 2, 1, 1], [2], [3]$ works.

In the sixth test case, the only possible split is $[2], [1], [2]$, but the left part does not work.

In the seventh test case, the split $[1], [2], [3]$ works.

In the eighth test case, the split $[1, 3], [3, 1], [1]$ works.

In the ninth test case, the split $[1], [1], [3, 3, 1]$ works.

In the tenth test case, the only possible split is $[1], [3], [1]$, but the middle part does not work.

前两个测试用例已在题目描述中说明。

在第三个测试用例中，左部分可以是 $[1]$，但此时无论中间部分选择 $[3]$、$[3, 3]$ 还是 $[3, 3, 2]$，均不满足条件。左部分也可以是 $[1, 3]$；此时中间部分必须为 $[3, 2]$，而右部分为空。因此，第三个样例的答案为 NO。

在第四个测试用例中，唯一有效的左部分是整个数组，因为对于任意非空且更短的前缀，数字 1 的个数均小于数字 2 的个数，因此中间部分和右部分无法同时非空。

在第五个测试用例中，划分 $[3, 2, 1, 2, 1, 1], [2], [3]$ 是可行的。

在第六个测试用例中，唯一可能的划分是 $[2], [1], [2]$，但左部分不满足条件。

在第七个测试用例中，划分 $[1], [2], [3]$ 是可行的。

在第八个测试用例中，划分 $[1, 3], [3, 1], [1]$ 是可行的。

在第九个测试用例中，划分 $[1], [1], [3, 3, 1]$ 是可行的。

在第十个测试用例中，唯一可能的划分是 $[1], [3], [1]$，但中间部分不满足条件。