题目描述

对于一个整数数组 $a_1, a_2, \dots, a_n$，我们定义其相等性特征为数组 $b_2, b_3, \dots, b_{n-1}$，其中当数组 $a$ 的第 $i$ 个元素与其两个相邻元素都相等时 $b_i = 1$，否则当数组 $a$ 的第 $i$ 个元素至少有一个相邻元素不相等时 $b_i = 0$。

例如，对于数组 $[1, 2, 2, 2, 3, 3, 4, 4, 4, 4]$，其相等性特征为 $[0, 1, 0, 0, 0, 0, 1, 1]$。

现在给定数组 $b_2, b_3, \dots, b_{n-1}$，你需要判断是否存在一个数组 $a$ 能够生成给定的相等性特征。

输入格式

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

每个测试用例包含两行：

• 第一行包含一个整数 $n$（$3 \le n \le 100$）；
• 第二行包含 $n-2$ 个整数 $b_2, b_3, \dots, b_{n-1}$（$0 \le b_i \le 1$）。

输出格式

对于每个测试用例，若存在符合条件的数组 $a$ 则输出 YES，否则输出 NO。字母可以任意大小写。

说明/提示

在第一个样例中，数组 $a = [1, 2, 2, 2, 3, 3, 4, 4, 4, 4]$ 符合条件。

在第二个样例中，数组 $a = [7, 7, 7]$ 符合条件。

翻译由 DeepSeek R1 完成

样例

3
10
0 1 0 0 0 0 1 1
3
1
10
0 1 0 1 1 0 0 1

YES
YES
NO