题目描述

给定一个由 $n$ 个整数构成的数组 $a$。

你的任务是判断 $a$ 是否存在长度至少为 $3$ 的回文子序列。

回忆一下，如果数组 $b$ 可以通过从数组 $a$ 中删除若干（可以为零）元素（不要求连续），且不改变剩余元素的顺序得到，则称 $b$ 是 $a$ 的一个子序列。例如，$[2]$、$[1, 2, 1, 3]$ 和 $[2, 3]$ 都是 $[1, 2, 1, 3]$ 的子序列，但 $[1, 1, 2]$ 和 $[4]$ 不是。

另外，回文数组是指正着读和反着读都相同的数组。换句话说，长度为 $n$ 的数组 $a$ 是回文的，当且仅当对于所有 $1 \leq i \leq n$，都有 $a_i = a_{n - i + 1}$。例如，$[1234]$、$[1, 2, 1]$、$[1, 3, 2, 2, 3, 1]$ 和 $[10, 100, 10]$ 都是回文数组，但 $[1, 2]$ 和 $[1, 2, 3, 1]$ 不是。

你需要回答 $t$ 组独立的测试用例。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

接下来的 $2t$ 行描述每个测试用例。每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 5000$），表示数组 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$），其中 $a_i$ 是数组 $a$ 的第 $i$ 个元素。

保证所有测试用例中 $n$ 的总和不超过 $5000$（$\sum n \leq 5000$）。

输出格式

对于每个测试用例，输出一行答案。如果 $a$ 存在长度至少为 $3$ 的回文子序列，输出 "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$ 的回文子序列。

由 ChatGPT 4.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

YES
YES
NO
YES
NO