CF1762G Unequal Adjacent Elements

给定一个由 $n$ 个正整数组成的数组 $a$。 请你找到 $[1,2,\dots,n]$ 的任意一个排列 $p$，使得： - 对于所有 $3 \leq i \leq n$，都有 $p_{i-2} < p_i$； - 对于所有 $2 \leq i \leq n$，都有 $a_{p_{i-1}} \neq a_{p_i}$。 如果不存在这样的排列，请输出不存在。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 3 \cdot 10^5$），表示数组 $a$ 的长度。 第二行包含 $n$ 个用空格分隔的整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq n$），表示数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每组测试用例，如果不存在满足条件的排列，输出 "NO"。否则，第一行输出 "YES"，第二行输出排列 $p$。 如果存在多个满足条件的排列，输出任意一个均可。 你可以以任意大小写输出 "YES" 和 "NO"（例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答）。

在第一个测试用例中，$p=[1,2,3]$ 是唯一满足条件的排列。 在第二个测试用例中，$[1,3,2,4]$、$[2,1,4,3]$ 以及其他一些排列也是可行的。 在第三个测试用例中，可以证明不存在任何满足条件的 $[1,2,3]$ 的排列。 由 ChatGPT 4.1 翻译