题目描述

一个数组 $[b_1, b_2, \ldots, b_m]$ 被称为回文数组，如果对于每个 $i$ 满足 $1 \leq i \leq m$，都有 $b_i = b_{m+1-i}$。空数组也被认为是回文数组。

如果一个数组满足以下条件，则称其为 kalindrome（卡林德数组）：

• 存在某个整数 $x$，可以删除数组中若干个等于 $x$ 的元素（可以不删，也可以删部分），使得剩下的数组（将剩余部分拼接起来）是回文数组。

注意，你不必删除所有等于 $x$ 的元素，也不必至少删除一个等于 $x$ 的元素。

例如：

• $[1, 2, 1]$ 是 kalindrome，因为你可以选择不删除任何元素，原数组就是回文数组。
• $[3, 1, 2, 3, 1]$ 是 kalindrome，因为你可以选择 $x = 3$，删除两个 $3$，得到 $[1, 2, 1]$，它是回文数组。
• $[1, 2, 3]$ 不是 kalindrome。

给定一个数组 $[a_1, a_2, \ldots, a_n]$，判断该数组是否为 kalindrome。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示数组的元素。

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

输出格式

对于每个测试用例，如果数组 $a$ 是 kalindrome，输出 YES，否则输出 NO。你可以用任意大小写输出答案。

说明/提示

在第一个测试用例中，数组 $[1]$ 已经是回文数组，因此也是 kalindrome。

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

在第三个测试用例中，不可能得到回文数组。

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

由 ChatGPT 4.1 翻译

样例

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

YES
YES
NO
YES