题目描述

给定一个仅包含数字 $1$、$2$ 和 $3$ 的数组 $a$。

请判断是否能将该数组划分为三个连续且非空的子段（分别记为第 $1$ 段、第 $2$ 段和第 $3$ 段），使得对于每个第 $i$ 段（$1 \le i \le 3$），满足以下条件：

• 该段中严格大于 $i$ 的元素个数，不超过该段总长度的一半。

换句话说，你需要将数组 $a$ 分割成左、中、右三个连续非空子段，满足：

• 左段：数字 $1$ 的数量大于等于数字 $2$ 和 $3$ 的数量之和；
• 中段：数字 $1$ 和 $2$ 的数量之和大于等于数字 $3$ 的数量；
• 右段：只需保证非空即可（因为不存在大于 $3$ 的数字）。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$3 \le n \le 2 \times 10^5$）—— 表示数组 $a$ 的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 3$）—— 表示数组的元素。

输出格式

对于每个测试用例，如果存在满足条件的划分方式，输出 YES；否则输出 NO。

样例输入 1

10
8
2 1 1 3 3 1 2 3
7
2 1 3 3 3 2 3
4
1 3 3 2
6
2 2 2 1 1 1
8
3 2 1 2 1 1 2 3
3
2 1 2
3
1 2 3
5
1 3 3 1 1
5
1 1 3 3 1
3
1 3 1

样例输出 1

YES
NO
NO
NO
YES
NO
YES
YES
YES
NO

说明

样例解释

• 在第 $1$ 个测试用例中，数组 $[2, 1, 1, 3, 3, 1, 2, 3]$ 可以划分为 $[2, 1, 1, 3]$、$[3, 1, 2]$ 和 $[3]$。
• 在第 $2$ 个测试用例中，数组无法进行合法的划分。
• 在第 $3$ 个测试用例中，如果左段为 $[1]$，那么中段无论怎么选（$[3]$、$[3, 3]$ 或 $[3, 3, 2]$）都不满足条件；如果左段为 $[1, 3]$，那么中段必须是 $[3, 2]$，导致右段为空。因此答案为 NO。
• 在第 $5$ 个测试用例中，一种合法的划分为 $[3, 2, 1, 2, 1, 1]$、$[2]$、$[3]$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于所有测试点，保证 $3 \le n \le 2 \times 10^5$。
• 对于所有测试点，保证 $1 \le a_i \le 3$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
• 保证所有的输入数值均为整数。