您有 $$$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”否则。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
442 3 4 132 3 153 4 1 2 553 1 4 2 5
输出复制
YESNOYESNO
注意
在第一个示例中,卡片的颜色为 $$$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}]$$$。