← 返回题目列表

Codeforces · 2069/A

A. 有数组吗?

中文机器翻译题面 查看原题

对于整数数组 $$$a_1, a_2, \dots, a_n$$$,我们定义它 平等特征 为数组 $$$b_2, b_3, \dots, b_{n-1}$$$,其中,如果数组 $$$a$$$ 的第 $$$i$$$ 元素等于其两个邻居,则 $$$b_i = 1$$$;如果数组的第 $$$i$$$ 元素等于其两个邻居,则 $$$b_i = 0$$$ $$$a$$$ 不等于至少一个邻居。

例如,对于数组 $$$[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$$$ 存在,或者 NO 如果这样的数组不存在。每个字母都可以在任何情况下打印。

示例

输入
复制

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

输出
复制

YES
YES
NO

注意

在第一个示例中,数组 $$$a = [1, 2, 2, 2, 3, 3, 4, 4, 4, 4]$$$ 是合适的。

在第二个示例中,数组 $$$a = [7, 7, 7]$$$ 是合适的。