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

Массив $$$[b_1, b_2, \ldots, b_m]$$$ является палиндромом, если $$$b_i = b_{m+1-i}$$$ для каждого $$$i$$$ от $$$1$$$ до $$$m$$$. Пустой массив также является палиндромом.

Массив называется калиндромом, если выполняется следующее условие:

  • Можно выбрать некоторое целое число $$$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$$$.

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

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

Пример
Входные данные
4
1
1
2
1 2
3
1 2 3
5
1 4 4 1 4
Выходные данные
YES
YES
NO
YES
Примечание

В первом наборе входных данных массив $$$[1]$$$ уже является палиндромом, поэтому он также является калиндромом.

Во втором наборе входных данных мы можем выбрать $$$x = 2$$$, удалить второй элемент и получить массив $$$[1]$$$, который является палиндромом.

В третьем наборе входных данных получить палиндром невозможно.

В четвертом наборе входных данных можно выбрать $$$x = 4$$$ и удалить пятый элемент, получив $$$[1, 4, 4, 1]$$$. Также можно выбрать $$$x = 1$$$, удалить первый и четвертый элементы и получить $$$[4, 4, 4]$$$.