题面翻译

对于一个长度为 $m$ 的序列 $b$，当且仅当对于所有的 $i\in[1,m]$，都有 $b_i=b_{m-i+1}$ 时，称其为回文序列。空序列也被认为是回文序列。

一个序列被称为「可爱的」，当且仅当满足以下条件：

• 存在一个数 $x$，使得删除序列中若干个等于 $x$ 的元素后，剩下的序列是回文序列。（删除元素后，剩下的元素会拼接在一起）

需要注意的是，并不需要删除所有等于 $x$ 的元素，也可以选择不删除任何元素。

例如：

• $[1,2,1]$ 是可爱的，因为不需要删除任何元素，它本身就是回文序列。
• $[3,1,2,3,1]$ 是可爱的，因为可以选择 $x=3$，删除所有等于 $3$ 的元素，剩下的序列变成回文序列。
• $[1,2,3]$ 不是可爱的。

现在给出一个长度为 $n$ 的序列 $a$，请判断它是否是可爱的。

本题有多组测试数据，共 $t$ 组，在输入开头给出。对于每组测试数据，如果序列 $a$ 是可爱的，请输出 YES，否则输出 NO。

题目数据满足：$1 \leq t \leq 10^4$，$1 \leq n \leq 2\times10^5$，$1 \leq a_i \leq n$，$1 \leq \sum n \leq 2\times10^5$。

输入格式

第一行包含一个整数 $t$ （$1 \le t \le 10^4$） —— 测试数据的组数。接下来是每组测试数据的描述。

每组测试数据的第一行包含一个整数 $n$ （$1 \le n \le 2 \cdot 10^5$） —— 数组的长度。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （$1 \le a_i \le n$） —— 数组的元素。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，如果数组 $a$ 是可爱的，则输出 YES，否则输出 NO。可以以任何大小写形式输出。

样例 #1

样例输入 #1

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

样例输出 #1

YES
YES
NO
YES

提示

第一组测试数据中，数组 $[1]$ 已经是回文的，因此也是可爱的。

第二组测试数据中，可以选择 $x = 2$ ，删除第二个元素，得到 $[1]$ ，它是回文的。

第三组测试数据中，无法得到回文序列。

第四组测试数据中，可以选择 $x = 4$ ，删除第五个元素，得到 $[1, 4, 4, 1]$ 。也可以选择 $x = 1$ ，删除第一个和第四个元素，得到 $[4, 4, 4]$ 。