← 返回比赛
已结束 GESP巅峰赛#33
← 上一题 下一题 →

A7328 | 双色序判定

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个由 $n$ 个两两不同整数组成的序列 $a$。

你需要把每个位置染成两种颜色之一。要求同时满足：

- 在原序列中，相邻两个位置颜色不同；
- 若把所有元素按数值从小到大重新排列，那么在这个新序列中，相邻两个元素的颜色仍然不同。

请判断是否存在这样的染色方案。

输入格式

第一行一个整数 $t$，表示测试组数。

对于每组数据：

- 第一行一个整数 $n$；
- 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

保证所有 $a_i$ 互不相同。

输出格式

对每组数据输出一行：

- 若存在合法染色，输出 YES；
- 否则输出 NO。

输入输出样例

输入 #1
4
4
2 3 4 1
3
2 3 1
5
3 4 1 2 5
5
3 1 4 2 5
输出 #1
YES
NO
YES
NO
C++ 编辑器
输入
输出