题目描述

有 $n$ 张卡片排成一行，第 $i$ 张卡片上写有整数 $a_i$，所有整数互不相同。

你需要将每张卡片染成红色或蓝色，且满足以下两个条件：

1. 原排列中，任意两个相邻的卡片颜色不同；
2. 将所有卡片按数字升序重新排列后，新排列中任意两个相邻的卡片颜色也不同。

请判断是否存在满足要求的染色方式。

输入格式

输入包含多组测试用例。第一行输入测试用例数 $t$（$1 \le t \le 200$）。

每组测试用例的第一行输入一个整数 $n$（$2 \le n \le 100$），表示数组的长度。 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

保证数组中所有元素互不相同。

输出格式

对于每组测试用例，若存在合法的染色方式，输出 YES，否则输出 NO。

输出的大小写不做要求（例如 yEs、yes、Yes、YES 均视为正确答案）。

说明/提示

第一个样例中，卡片的染色方式为 $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}]$。两种排列均满足相邻颜色不同的条件，因此答案为 YES。

第二个样例中，不存在合法的染色方式。例如，若将卡片染为 $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}]$，满足所有条件。

样例

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