← 返回题目列表

Codeforces · 2233/D

D. 货架上的商品

中文机器翻译题面 查看原题

在超市里,同类型的商品通常会并排放置,这样货架看起来整齐,顾客也更容易找到自己需要的东西。

货架由 $$$n$$$ 元素组成的数组 $$$a$$$ 描述,其中 $$$a_i$$$ 是位置 $$$i$$$ 处商品的类型。

如果对于每两个位置 $$$i$$$ 和 $$$j$$$ 使得 $$$1 \le i \lt j \le n$$$ 和 $$$a_i = a_j$$$,我们会说货架排列正确:对于从 $$$i$$$ 到 $$$j$$$ 的每个 $$$k$$$,$$$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,如果无法正确排列货架;
  • 是,是否可以使货架正确排列,最多将两种商品互换一次。

任何情况下都可以输出答案。例如,“是的", "是", "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$$$位置的货物交换,之后货架就会正确排列。