分数: 800 点
问题陈述
考虑对一系列操作执行以下操作 N 正整数 A = (A_1, A_2, \ldots, A_N) 获取序列 I = (i_1, i_2, \ldots, i_K).
- 对于每个 k = 1, 2, \ldots, K 按照此顺序,执行以下操作。
- 选择一个 i 这样 A_i = \min\{A_1, A_2, \ldots, A_N\}.
- 让 i_k = i.
- 添加 1 to A_i.
给你整数 N, K,以及一个序列 I.
判断是否存在正整数序列 A 可以获得 I 来自操作。如果存在,找到字典顺序最小的这样的序列。
约束
- 1\leq N, K\leq 3\times 10^5
- 1\leq i_k\leq N
输入
输入由标准输入按以下格式给出:
N K i_1 i_2 \ldots i_K
输出
如果不存在正整数序列 A 可以获得 I 运行后,打印 -1。
如果存在,则打印此类序列中按字典顺序最小的序列 A,在一行中,之间有空格。
示例输入 1
4 6 1 1 4 4 2 1
示例输出 1
1 3 3 2
可以获得的一些序列 I = (1,1,4,4,2,1) 从操作是 (1, 3, 3, 2) 和 (2, 4, 5, 3)。其中按字典顺序最小的是 (1, 3, 3, 2).
示例输入 2
4 6 2 2 2 2 2 2
示例输出 2
6 1 6 6
示例输入 3
4 6 1 1 2 2 3 3
示例输出 3
-1