← 返回题目列表

AtCoder · arc130_e

E. 增加最小值

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

分数: 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