在超市里,同类型的商品通常会并排放置,这样货架看起来整齐,顾客也更容易找到自己需要的东西。
货架由 $$$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”也将被接受。
示例
输入复制
731 2 127 761 2 3 1 2 361 1 2 3 2 371 2 3 1 2 3 461 2 1 2 1 161 2 2 3 3 1
输出复制
YESYESNOYESNOYESNO
注意
在第一个示例中,您可以交换位置 $$$1$$$ 和 $$$2$$$ 处的货物,之后货架将如下所示:$$$[2, 1, 1]$$$。
在第二个示例中,架子已正确排列。
在第三个示例中,不可能通过一次交换来正确排列货架。
在第六个示例中,您可以将$$$1$$$和$$$4$$$位置的货物交换,之后货架就会正确排列。