[ONTAK 2026] 非常饥饿的蜥蜴

题目描述

Bytek 收藏了许多非常饥饿的蜥蜴。他有 $n$ 只蜥蜴，它们的大小恰好分别为 $1,2,\ldots,n$。Bytek 可以把这些蜥蜴按任意顺序排成一行放入展示缸中。

放入展示缸后，每一秒都会发生如下过程：

• 所有蜥蜴同时行动；
• 如果一只蜥蜴左边紧邻着一只比它更小的蜥蜴，那么它会吃掉这只左邻居；
• 本秒所有捕食行为结束后，被吃掉的蜥蜴消失，其余蜥蜴重新紧密排列；
• 如果某一秒开始时已经没有任何蜥蜴能够吃掉自己的左邻居，则整个过程结束。

注意，一只蜥蜴可以在同一秒中既吃掉左边的蜥蜴，又被右边的蜥蜴吃掉。

例如，若初始排列为

(1,3,2,4,5)，

则：

• 第 $1$ 秒中，蜥蜴 $3$ 吃掉 $1$，蜥蜴 $4$ 吃掉 $2$，同时蜥蜴 $5$ 吃掉 $4$。这一秒结束后排列变为 (3,5)；
• 第 $2$ 秒中，蜥蜴 $5$ 吃掉 $3$，排列变为 (5)；
• 此时过程结束。

---

Bytek 还给出了一个长度为 $n$ 的序列

$(a_1,a_2,\ldots,a_n)$。

这里的下标 $i$ 表示的是初始排列中的位置，而不是蜥蜴的大小。

具体来说：

• 若 $a_i>0$，则要求初始时位于第 $i$ 个位置的蜥蜴恰好在第 $a_i$ 秒被吃掉；
• 若 $a_i=-1$，则要求初始时位于第 $i$ 个位置的蜥蜴一直存活到整个过程结束。

如果一个初始排列满足上述所有要求，就称它为一个美观排列。

---

接下来定义美观排列之间的大小关系。

对于一个排列 $p=(p_1,p_2,\ldots,p_n)$，记 $\operatorname{pos}_p(x)$ 表示大小为 $x$ 的蜥蜴在排列 $p$ 中的位置。

比较两个排列 $p$ 和 $q$ 时，按照下面两个序列的字典序进行比较：

$(\operatorname{pos}_p(1),\operatorname{pos}_p(2),\ldots,\operatorname{pos}_p(n))$

和

$(\operatorname{pos}_q(1),\operatorname{pos}_q(2),\ldots,\operatorname{pos}_q(n))$。

也就是说，找到最小的大小 $x$，使得大小小于 $x$ 的所有蜥蜴在两个排列中的位置都相同。如果

$\operatorname{pos}_p(x)<\operatorname{pos}_q(x)$，

那么认为 $p<q$。

你的任务是求按照上述顺序排列后的第 $k$ 个美观排列。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

数据保证：

• $1\le n\le 10^5$；
• $1\le k\le 10$；
• $-1\le a_i\le n$；
• $a_i\ne0$。

输出格式

如果至少存在 $k$ 个美观排列，输出一行 $n$ 个整数

$b_1,b_2,\ldots,b_n$，

其中 $b_i$ 表示第 $k$ 小的美观排列中，初始时位于第 $i$ 个位置的蜥蜴大小。

如果不存在第 $k$ 个美观排列，输出：

-1

样例 1

5 1
1 2 1 -1 -1

1 3 2 5 4

样例 1 说明

初始排列为

(1,3,2,5,4)。

第 $1$ 秒：

• 蜥蜴 $3$ 吃掉 $1$；
• 蜥蜴 $5$ 吃掉 $2$。

排列变为

(3,5,4)。

第 $2$ 秒：

• 蜥蜴 $5$ 吃掉 $3$。

排列变为

(5,4)，

之后不再有蜥蜴能够吃掉左邻居，过程结束。

因此，按照初始位置来看：

初始位置	蜥蜴大小	被吃时间
1
2	3	2
3	2	1
4	5	$-1$
5	4

恰好得到序列

1 2 1 -1 -1。

样例 2

5 10
1 2 1 -1 -1

-1

子任务

子任务	限制	分值
1	$n\le9$	7
2	$n\le2000$	25
3	$k=1$	31
4	$k\le2$	18
5	无额外限制	19