← 返回题目列表

Codeforces · 2191/A

A. 数组着色

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

您有 $$$n$$$ 卡片排成一排。第 $$$i$$$ 卡上写有整数 $$$a_i$$$。所有整数都是不同的。

您必须为每张卡片着色 $$$\color{red}{\text{red}}$$$ 或 $$$\color{blue}{\text{blue}}$$$,以满足以下条件:

  • 该行中任意两张相邻的卡片具有不同的颜色。
  • 如果您重新排列卡片,使其上的数字按升序排列,则新行中任何两张相邻的卡片也必须具有不同的颜色。

确定是否存在这种着色。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 200$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。

保证 $$$a$$$ 的所有元素都是不同的。

输出

对于每个测试用例,输出“是“如果你可以给卡片上色以满足条件,并且”NO”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

4
4
2 3 4 1
3
2 3 1
5
3 4 1 2 5
5
3 1 4 2 5

输出
复制

YES
NO
YES
NO

注意

在第一个示例中,卡片的颜色为 $$$a = [\color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{1}]$$$。排序后,卡片变为$$$[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}]$$$。两个序列都满足条件,所以答案是 是.

在第二个示例中,不存在有效的着色。例如,如果我们将卡片着色为 $$$a = [\color{blue}{2}, \color{red}{3}, \color{blue}{1}]$$$,则排序序列将变为 $$$[\color{blue}{1}, \color{blue}{2}, \color{red}{3}]$$$。这里,相邻元素$$$1$$$和$$$2$$$具有相同的颜色,因此不满足条件。

在第三个示例中,可能的颜色是 $$$a = [\color{blue}{3}, \color{red}{4}, \color{blue}{1}, \color{red}{2}, \color{blue}{5}]$$$。排序后,卡片变为$$$[\color{blue}{1}、\color{red}{2}、\color{blue}{3}、\color{red}{4}、\color{blue}{5}]$$$。