镜序筛选

题目背景

湖心岛上有一台“镜序检测仪”。

乐柠兔把一串编号依次放入仪器中，仪器会尝试让这串编号呈现出“左右对称”的镜像结构。噜噜补充说：仪器的清理机制很特殊——它只能针对某一种编号进行删减，而且删多少都可以，甚至可以一张都不删。

题目描述

给定一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$。

我们称一个数组是 回文数组，当它满足：对所有 $1 \le i \le m$，都有第 $i$ 个元素等于第 $m+1-i$ 个元素。

空数组也视为回文数组。

现在定义一种更宽松的“镜序数组”：

你可以先选择一个整数 $x$，然后从原数组中删除若干个值等于 $x$ 的元素（可以删 0 个，也可以不删完），把剩下的元素按原相对顺序拼接起来。

如果最终得到的数组是回文数组，则称原数组是 镜序数组。

请你判断给定数组是否为镜序数组。

输入格式

第一行输入一个整数 $t$，表示测试用例数量。

接下来每个测试用例：

• 第一行输入一个整数 $n$，表示数组长度。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示数组元素。

输出格式

对每个测试用例输出一行：

若该数组是镜序数组，输出 YES；否则输出 NO。

输入输出样例

输入

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

输出

YES
YES
NO
YES

数据范围与约定

对于 100% 的数据保证：

• $1 \le t \le 10^4$
• $1 \le n \le 2\times 10^5$
• $1 \le a_i \le n$
• 所有测试用例的 $n$ 之和不超过 $2\times 10^5$