题目描述

在超市中，相同类型的商品通常会被放在一起，这样可以让货架看起来整齐，也方便顾客找到所需的商品。

用一个长度为 $n$ 的数组 $a$ 描述货架，其中 $a_i$ 表示第 $i$ 个位置的商品类型。

如果对于所有满足 $1 \le i < 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 \times 10^5$），表示货架商品的数量。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示第 $i$ 个位置上的商品类型。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出描述

对于每个测试用例，输出一行：如果可能通过至多一次交换使货架排列正确，输出 YES，否则输出 NO。

样例

3
3
1 2 1
2
7 7
6
1 2 3 1 2 3

YES
YES
NO

注释

对于第一组测试用例，可以交换第 $1$ 个和第 $2$ 个商品，此时货架变为 $[2, 1, 1]$，满足要求。