货架上的商品

ID: 18545

传统题

2000ms

512MiB

难度: 10

上传者:

标签>

数据结构

暴力

实现

双指针

题目描述

超市货架用数组 $a$ 描述，其中 $a_i$ 表示第 $i$ 个位置上商品的类型。

如果每一种类型的商品都形成一个连续区间，则称货架摆放正确。也就是说，对于任意 $i\lt j$ 且 $a_i=a_j$ ，区间 $[i,j]$ 内的所有商品类型都必须等于 $a_i$ 。

你最多可以选择两个不同位置交换一次，也可以不交换。判断是否能让货架摆放正确。

第一行包含整数 $t$ ，表示测试组数。

每组测试数据第一行包含整数 $n$ 。

第二行包含 $n$ 个整数 $a_i$ 。

对每组测试数据，如果可以通过至多一次交换使货架正确，输出 YES；否则输出 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$ 上的货物，之后货架将被正确排列。