← 返回题目列表

Codeforces · 1610/B

B. Kalindrome 阵列

中文机器翻译题面 查看原题

数组 $$$[b_1, b_2, \ldots, b_m]$$$ 是回文,如果 $$$b_i = b_{m+1-i}$$$ 对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$i$$$。空数组也是回文数组。

如果满足以下条件,则数组称为回数列:

- 可以选择一些整数 $$$x$$$ 并删除数组中等于 $$$x$$$ 的一些元素,以便剩余的数组(将剩余部分粘合在一起之后)是回文。

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

例如:

- $$$[1, 2, 1]$$$ 是回数列,因为你根本无法删除单个元素。
- $$$[3, 1, 2, 3, 1]$$$ 是回文,因为你可以选择 $$$x = 3$$$ 并删除等于 $$$3$$$ 的两个元素,得到数组 $$$[1, 2, 1]$$$,这是一个回文。
- $$$[1, 2, 3]$$$ 不是回历。

给你一个数组 $$$[a_1, a_2, \ldots, a_n]$$$。确定 $$$a$$$ 是否为回数。

输入

第一行包含一个整数 $$$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

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]$$$。