← 返回题目列表

Codeforces · 1887/F

F. 最小段

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

您有一个序列 $$$a_1, a_2, \ldots, a_n$$$ 由从 $$$1$$$ 到 $$$n$$$ 的整数组成,不一定不同。由于某种未知的原因,您决定计算序列的以下特征:

- 令 $$$r_i$$$ ($$$1 \le i \le n$$$) 为最小的 $$$j \ge i$$$,以便在子段 $$$a_i, a_{i+1}, \ldots, a_j$$$ 上出现序列 $$$a$$$ 中的所有不同数字。更正式地说,对于 [1, n]$$$ 中的任意 $$$k,[i, j]$$$ 中存在 $$$l \,使得 $$$a_k = a_l$$$。如果这样的$$$j$$$不存在,则认为$$$r_i$$$等于$$$n+1$$$。
- 序列 $$$a$$$ 的特征定义为序列 $$$r_1, r_2, \ldots, r_n$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 丢失序列 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$ ($$$i \le r_i \le n+1$$$) — 丢失序列 $$$a$$$ 的特征。

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

输出

对于每个测试用例,输出以下内容:

- 如果不存在具有特征 $$$r$$$ 的序列 $$$a$$$,则打印“No”。
- 否则,在第一行打印“Yes”,并在第二行打印与特征 $$$r$$$ 匹配的任意整数序列 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。

示例

输入 #1

5
3
2 3 4
5
2 3 5 4 6
1
1
3
1 3 4
8
3 6 6 6 8 9 9 9

输出 #1

Yes
1 2 1
No
Yes
1 
No
Yes
1 3 5 3 5 1 1 3

注意

在第一个测试用例中,序列 $$$a = [1, 2, 1]$$$ 是合适的。整数 $$$1$$$ 和 $$$2$$$ 出现在子段 $$$[1, 2]$$$ 和 $$$[2, 3]$$$ 上。

在第二个测试用例中,可以证明不存在合适的序列$$$a$$$。