D. Товары на полке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В супермаркете товары одного вида стараются выставлять подряд, чтобы полка выглядела аккуратно и покупателям было проще искать нужное.

Полка описывается массивом $$$a$$$ из $$$n$$$ элементов, где $$$a_i$$$ — вид товара на позиции $$$i$$$.

Будем считать, что полка оформлена правильно, если для каждых двух позиций $$$i$$$ и $$$j$$$ таких, что $$$1 \le i \lt j \le n$$$ и $$$a_i = a_j$$$, выполняется следующее условие: для каждого $$$k$$$ от $$$i$$$ до $$$j$$$ верно $$$a_k = a_i$$$. Иными словами, товары каждого вида на полке должны располагаться одним непрерывным блоком.

Разрешается не более одного раза выбрать два различных индекса и обменять местами товары на этих позициях. Можно и не делать обмен вовсе.

Определите, можно ли после этого добиться того, чтобы полка была оформлена правильно.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$) — количество товаров на полке.

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^{9}$$$), где $$$a_{i}$$$ обозначает вид товара на позиции $$$i$$$.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^{5}$$$.
Выходные данные

Для каждого набора входных данных выведите одно из двух:

  • NO, если невозможно оформить полку правильно;
  • YES, если можно сделать полку оформленной правильно не более чем одним обменом двух товаров.

Ответ вы можете выводить в любом регистре. Так, например, «YeS», «YES», «NO», «nO» будут также приняты.

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

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

Во втором примере полка уже оформлена правильно.

В третьем примере невозможно с помощью одного обмена правильно оформить полку.

В шестом примере можно обменять товары на позициях $$$1$$$ и $$$4$$$, после этого полка будет оформлена правильно.