Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

B. Еще одна задача про палиндромы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел.

Ваша задача — определить, содержит ли $$$a$$$ какую-то подпоследовательность длины хотя бы $$$3$$$, которая является палиндромом.

Напомним, что массив $$$b$$$ называется подпоследовательностью массива $$$a$$$, если $$$b$$$ может быть получен удалением некоторого (возможно, нулевого) количества элементов из $$$a$$$ (не обязательно подряд идущих) без изменения порядка оставшихся элементов. Например, $$$[2]$$$, $$$[1, 2, 1, 3]$$$ и $$$[2, 3]$$$ являются подпоследовательностями $$$[1, 2, 1, 3]$$$, а $$$[1, 1, 2]$$$ и $$$[4]$$$ — нет.

Также напомним, что палиндром — это массив, который читается одинаково как слева направо, так и справа налево. Другими словами, массив $$$a$$$ длины $$$n$$$ является палиндромом, если $$$a_i = a_{n - i - 1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$. Например, массивы $$$[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$$$ является $$$i$$$-м элементом $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$5000$$$ ($$$\sum n \le 5000$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ — «YES» (без кавычек), если $$$a$$$ содержит какую-то подпоследовательность длины хотя бы $$$3$$$, которая является палиндромом, и «NO» в противном случае.

Пример
Входные данные
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
Примечание

В первом наборе тестовых данных из примера массив $$$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$$$, которые являются палиндромами.