← 返回题目列表

Codeforces · 1762/G

G. 不相等的相邻元素

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

给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。

找到 $$$[1,2,\dots,n]$$$ 的任意排列 $$$p$$$ 使得:

- $$$p_{i-2} < p_i$$$ 对于所有 $$$i$$$,其中 $$$3 \leq i \leq n$$$,并且
- $$$a_{p_{i-1}} \neq a_{p_i}$$$ 对于所有 $$$i$$$,其中 $$$2 \leq i \leq n$$$。

或者报告不存在这样的排列。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — representing the array $$$a$$$.

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

输出

For each test case, output "NO" if no such permutation exists, otherwise output "YES" in the first line and print the permutation $$$p$$$ in the next line.

如果有多种排列,则打印其中任何一种。

You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).

示例

输入 #1

4
3
1 2 1
4
1 2 3 4
3
1 1 1
7
1 2 1 1 3 1 4

输出 #1

YES
1 2 3
YES
3 1 4 2
NO
YES
1 2 3 5 4 7 6

注意

在第一个测试用例中,$$$p=[1,2,3]$$$ 是满足给定约束的$$$[1,2,3]$$$ 的唯一排列。

在第二个测试用例中,$$$[1,3,2,4]$$$、$$$[2,1,4,3]$$$ 和其他一些排列也是可以接受的。

In the third test case, it can be proved that there does not exist any permutation of $$$[1,2,3]$$$ satisfying the given constraints.