CF2233D.Goods on the Shelf

In a supermarket, goods of the same type are usually placed next to each other so that the shelf looks neat and it is easier for customers to find what they need.

The shelf is described by an array $a$ of $n$ elements, where $a_i$ is the type of the good at position $i$.

We will say that the shelf is arranged correctly if for every two positions $i$ and $j$ such that $1 \le i \lt j \le n$ and $a_i = a_j$, the following condition holds: for each $k$ from $i$ to $j$, it is true that $a_k = a_i$. In other words, goods of each type on the shelf must form one contiguous block.

You are allowed to choose two different positions at most once and swap the goods at these positions. You may also choose not to perform any swap.

Determine whether it is possible to make the shelf arranged correctly after that.

在超市中，相同类型的商品通常被放置在相邻的位置，以使货架看起来整齐，并方便顾客找到所需的商品。

货架由一个包含 $n$ 个元素的数组 $a$ 描述，其中 $a_i$ 表示位置 $i$ 处商品的类型。

我们称货架排列正确，当且仅当对任意两个满足 $1 \le i \lt j \le n$ 且 $a_i = a_j$ 的位置 $i$ 和 $j$，以下条件成立：对每个从 $i$ 到 $j$ 的 $k$，均有 $a_k = a_i$。换言之，货架上每种类型的商品必须构成一个连续的块。

你最多可以执行一次操作：选择两个不同的位置，并交换这两个位置上的商品。你也可以选择不执行任何交换。

请判断：是否可以通过上述操作（或不操作）使货架排列正确。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 2 \cdot 10^{5}$) — the number of goods on the shelf.

The second line of each test case contains $n$ integers $a_{i}$ ($1 \le a_{i} \le 10^{9}$), where $a_{i}$ denotes the type of the good at position $i$.

Additional input constraints:

• the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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}$。

For each test case, output one of the following:

• NO, if it is impossible to arrange the shelf correctly;
• YES, if it is possible to make the shelf arranged correctly with at most one swap of two goods.

You may output the answer in any case. For example, "YeS", "YES", "NO", "nO" will also be accepted.

对于每个测试用例，输出以下之一：

• NO，如果无法正确排列货架；
• YES，如果最多交换两个商品即可使货架正确排列。

您可以以任意大小写形式输出答案。例如，YeS、YES、NO、nO 均可被接受。

In the first example, you can swap the goods at positions $1$ and $2$, after which the shelf will look like this: $[2, 1, 1]$.

In the second example, the shelf is already arranged correctly.

In the third example, it is impossible to arrange the shelf correctly with one swap.

In the sixth example, you can swap the goods at positions $1$ and $4$, after which the shelf will be arranged correctly.

在第一个例子中，你可以交换位置 $1$ 和 $2$ 处的商品，交换后货架将变为：$[2, 1, 1]$。

在第二个例子中，货架已经正确排列。

在第三个例子中，仅通过一次交换无法使货架正确排列。

在第六个例子中，你可以交换位置 $1$ 和 $4$ 处的商品，交换后货架将正确排列。