CF1610B.Kalindrome Array

An array $[b_1, b_2, \ldots, b_m]$ is a palindrome, if $b_i = b_{m+1-i}$ for each $i$ from $1$ to $m$. Empty array is also a palindrome.

An array is called kalindrome, if the following condition holds:

• It's possible to select some integer $x$ and delete some of the elements of the array equal to $x$, so that the remaining array (after gluing together the remaining parts) is a palindrome.

Note that you don't have to delete all elements equal to $x$, and you don't have to delete at least one element equal to $x$.

For example :

• $[1, 2, 1]$ is kalindrome because you can simply not delete a single element.
• $[3, 1, 2, 3, 1]$ is kalindrome because you can choose $x = 3$ and delete both elements equal to $3$, obtaining array $[1, 2, 1]$, which is a palindrome.
• $[1, 2, 3]$ is not kalindrome.

You are given an array $[a_1, a_2, \ldots, a_n]$. Determine if $a$ is kalindrome or not.

数组 $[b_1, b_2, \ldots, b_m]$ 称为回文数组，当且仅当对每个从 $1$ 到 $m$ 的 $i$，均有 $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]$。请判断 $a$ 是否为 kalindrome。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — elements of the array.

It's guaranteed that the sum of $n$ over all test cases won't exceed $2 \cdot 10^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$。

For each test case, print YES if $a$ is kalindrome and NO otherwise. You can print each letter in any case.

对于每个测试用例，如果 $a$ 是 kalindrome，则输出 YES；否则输出 NO。字母的大小写不限。

In the first test case, array $[1]$ is already a palindrome, so it's a kalindrome as well.

In the second test case, we can choose $x = 2$, delete the second element, and obtain array $[1]$, which is a palindrome.

In the third test case, it's impossible to obtain a palindrome.

In the fourth test case, you can choose $x = 4$ and delete the fifth element, obtaining $[1, 4, 4, 1]$. You also can choose $x = 1$, delete the first and the fourth elements, and obtain $[4, 4, 4]$.

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

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

在第三个测试用例中，无法得到回文数组。

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