题目描述

给定一个由 $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$。
  • 将 $A_i$ 加 $1$。

给定整数 $N, K$ 和序列 $I$。

请判断是否存在一个正整数序列 $A$，使得按照上述操作能够得到序列 $I$。如果存在，请输出字典序最小的这样的序列 $A$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$ $i_1$ $i_2$ $\ldots$ $i_K$

输出格式

如果不存在满足条件的正整数序列 $A$，输出 -1。
如果存在，输出字典序最小的正整数序列 $A$，用空格分隔，输出一行。

样例 1

输入

4 6
1 1 4 4 2 1

输出

1 3 3 2

样例 2

输入

4 6
2 2 2 2 2 2

输出

6 1 6 6

样例 3

输入

4 6
1 1 2 2 3 3

输出

-1

说明/提示

限制条件

• $1 \leq N, K \leq 3 \times 10^5$
• $1 \leq i_k \leq N$

样例解释 1

作为能够通过操作得到 $I = (1, 1, 4, 4, 2, 1)$ 的正整数序列 $A$，有 $(1, 3, 3, 2)$、$(2, 4, 5, 3)$ 等。其中字典序最小的是 $(1, 3, 3, 2)$。

由 ChatGPT 4.1 翻译