给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。
你的任务是确定 $$$a$$$ 是否有一些长度至少为 $$$3$$$ 的回文子序列。
回想一下,如果 $$$b$$$ 可以通过从 $$$a$$$ 中删除一些(可能是零)元素(不一定是连续的)而不改变剩余元素的顺序来获得,则数组 $$$b$$$ 被称为数组 $$$a$$$ 的子序列。例如,$$$[2]$$$、$$$[1, 2, 1, 3]$$$ 和 $$$[2, 3]$$$ 是 $$$[1, 2, 1, 3]$$$ 的子序列,但 $$$[1, 1, 2]$$$ 和 $$$[4]$$$ 不是。
另外,回文是一个向后读取与向前读取相同的数组。换句话说,如果 $$$a_i = a_{n - i - 1}$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$,则长度为 $$$n$$$ 的数组 $$$a$$$ 是回文。例如,数组 $$$[1234]$$$、$$$[1, 2, 1]$$$、$$$[1, 3, 2, 2, 3, 1]$$$ 和 $$$[10, 100, 10]$$$ 是回文,但数组 $$$[1, 2]$$$ 和 $$$[1, 2, 3, 1]$$$ 不是。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
接下来的 $$$2t$$$ 行描述了测试用例。测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5000$$$) — $$$a$$$ 的长度。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$ ($$$\sum n \le 5000$$$)。
输出
对于每个测试用例,如果 $$$a$$$ 有一些长度至少为 $$$3$$$ 的回文子序列,则打印答案“YES”(不带引号),否则打印“NO”。
示例
输入 #1
5 3 1 2 1 5 1 2 2 3 2 3 1 1 2 4 1 2 2 1 10 1 1 2 2 3 3 4 4 5 5
输出 #1
YES YES NO YES NO
注意
在示例的第一个测试用例中,数组 $$$a$$$ 有一个子序列 $$$[1, 2, 1]$$$,它是一个回文。
在示例的第二个测试用例中,数组 $$$a$$$ 有两个长度为 $$$3$$$ 的回文子序列:$$$[2, 3, 2]$$$ 和 $$$[2, 2, 2]$$$。
在示例的第三个测试用例中,数组 $$$a$$$ 没有长度至少为 $$$3$$$ 的回文子序列。
在示例的第四个测试用例中,数组 $$$a$$$ 有一个长度为 $$$4$$$ 的回文子序列:$$$[1, 2, 2, 1]$$$ (并且有两个长度为 $$$3$$$ 的回文子序列:均为 $$$[1, 2, 1]$$$)。
在示例的第五个测试用例中,数组 $$$a$$$ 没有长度至少为 $$$3$$$ 的回文子序列。