这题太神仙了吧！感觉还不是很懂，但是尽力理一下思路。
设 \(t_x\) 为最大的 \(j\) 使得 \(i_j = x\)，不存在则 \(t_x = 0\)。
设 \(1 \sim n\) 的数按照 \(t\) 从小到大排序后是 \(p_1, p_2, ..., p_n\)，设 \(q_i\) 为 \(i\) 在 \(p\) 中的排名，即 \(q_{p_i} = i\)。
发现正着不好考虑，不妨最小化操作之后的序列字典序，这与原问题等价（操作对每个数加的值是定值）。
下面的讨论设 \(a_i\) 为 \(p_i\) 位置上的数。
在第一次操作前，容易发现使 \(\min\limits_{i=1}^n a_i = 1\) 最优。因为若 \(\min\limits_{i=1}^n a_i > 1\)，可以把所有数减去 \((\min\limits_{i=1}^n a_i) - 1\)。
但是这样的限制太宽了。根据题目操作的性质，观察有没有更紧的限制。
大概感受一下，如果所有操作都结束了，显然我们希望 \(a_i\) 越紧凑越好，即理想状态是 \(\max\limits_{i=1}^n a_i - \min\limits_{i=1}^n a_i \le 1\)。事实上如果存在解，那么一定存在一组解满足这个条件，且这个解就是最优解。思考这是为什么。
考察所有操作都结束后，\(a_{i-1}\) 和 \(a_i\) 的大小关系（不妨先假设 \(p_{i-1}\) 被操作过）。
-
当 \(a_i\) 最后一次操作之前，\(a_i\) 是序列的最小值。那我们得到 \(a_i - 1 \le a_{i-1}\)。
-
在 \(a_{i-1}\) 最后一次操作前，\(a_{i-1}\) 是序列的最小值，并且 \(a_{i-1}\) 最后一次操作后，能使得 \(a_i\) 还能被操作。那我们得到 \(a_{i-1} \le a_i\)。
那我们得到 \(a_i - 1 \le a_{i-1} \le a_i\)。这是一条很强的限制。
事实上对于任意 \(i < j\)，\(a_j - 1 \le a_i \le a_j\)。并且对于没有被操作过的数，它们的 \(a_i \ge a_n - 1\)（显然取 \(a_i = a_n - 1\) 最优）。综上，我们得到 \(a_n - 1 \le a_1 \le a_2 \le \cdots \le a_n\)。
观察这个不等式，显然最终结果中只有一个符号是 \(<\)，其他都是 \(=\)。枚举 \(<\) 号的位置，取字典序最小值，就能做平方了。但是还不够。
不妨先假设 \(a_1 = a_2 = \cdots = a_n = 0\)，然后逆序操作，要求第 \(k\) 次操作后，\(a_{i_k}\) 为序列最小值。
考虑进行了第 \(k\) 次操作 \(u = i_k\)，这时候序列的最小值是 \(a_v\)（如果有多个就取 \(q_v\) 最小的）：
- 如果 \(u = v\)，那么操作合法，直接进行下一个操作；
- 如果 \(u \ne v \land a_u = a_v\)，那么 \(q_u > q_v\)。我们希望最后 \(u \sim v\) 之间都是 \(=\) 号，否则 \(a_u\) 就不能成为最小值了；
- 如果 \(a_u = a_v + 1\)：
- 如果 \(q_u < q_v\)，那么 \(u\) 还有救，只要保证 \(u \sim v\) 之间存在一个 \(<\) 号；
- 否则没救了，无解。
- 如果 \(a_u \ge a_v + 2\)，那也没救了，无解。
那么最后我们得到了若干个位置必须放 \(=\) 号，若干的位置可以放 \(<\)。
要使字典序越小得先让最小值最大（现在的最小值只能是负数，这样后面加的就越少）。在最小值最大的前提，我们还希望小于号尽量靠后（要使字典序最小）。
设 \(x\) 为逆序操作后，\(a\) 序列中的最小值的位置（如果有多个最小值就取 \(q_x\) 最小的）。那么最后小于号在 \(q_x\) 之前，最小值最大，如果 \(q_x\) 前面都不能放小于号了，那只能在它后面放；如果没有位置可以放小于号，就是无解。
那么最后能确定字典序最小的情况下 \(a_i\) 的相对大小关系，加上一个最小的数使得 \(a_i\) 都为正数，就是最后的解。
时间复杂度线性对数。瓶颈在逆序操作时的查询最小值。
code
// Problem: E - Increasing Minimum
// Contest: AtCoder - AtCoder Regular Contest 130
// URL: https://atcoder.jp/contests/arc130/tasks/arc130_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 300100;
int n, m, a[maxn], b[maxn], p[maxn], q[maxn];
int c[maxn], d[maxn], ans[maxn];
struct node {
int x, y, id;
node(int a = 0, int b = 0, int c = 0) : x(a), y(b), id(c) {}
};
inline bool operator < (const node &a, const node &b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d", &a[i]);
b[a[i]] = i;
}
for (int i = 1; i <= n; ++i) {
p[i] = i;
}
sort(p + 1, p + n + 1, [&](int x, int y) {
return b[x] < b[y];
});
for (int i = 1; i <= n; ++i) {
q[p[i]] = i;
}
set<node> st;
for (int i = 1; i <= n; ++i) {
st.emplace(0, q[i], i);
}
for (int i = m; i; --i) {
int x = a[i];
st.erase(node(c[x], q[x], x));
--c[x];
st.emplace(c[x], q[x], x);
node p = *st.begin();
int y = p.id;
if (x == y) {
continue;
}
if (c[x] == c[y]) {
++d[q[y]];
--d[q[x]];
} else if (c[x] == c[y] + 1) {
if (q[x] < q[y]) {
++d[1];
--d[q[x]];
++d[q[y]];
} else {
puts("-1");
return;
}
} else {
puts("-1");
return;
}
}
for (int i = 1; i <= n; ++i) {
d[i] += d[i - 1];
}
int pos = -1, mx = -1, rk = -1;
for (int i = 1; i <= n; ++i) {
if (-c[i] > mx) {
mx = -c[i];
rk = q[i];
} else if (-c[i] == mx) {
rk = min(rk, q[i]);
}
}
for (int i = rk - 1; i; --i) {
if (!d[i] && pos == -1) {
pos = i;
}
}
for (int i = n; i >= rk; --i) {
if (!d[i] && pos == -1) {
pos = i;
}
}
if (pos == -1) {
puts("-1");
return;
}
// printf("pos: %d\n", pos);
// for (int i = 1; i <= n; ++i) {
// printf("%d ", c[p[i]]);
// }
// putchar('\n');
for (int i = 1; i <= pos; ++i) {
ans[p[i]] = -1;
}
for (int i = 1; i <= n; ++i) {
ans[i] += c[i];
}
// for (int i = 1; i <= n; ++i) {
// printf("%d ", ans[i]);
// }
// putchar('\n');
int k = *min_element(ans + 1, ans + n + 1);
for (int i = 1; i <= n; ++i) {
ans[i] -= k - 1;
}
for (int i = 1; i <= n; ++i) {
printf("%d ", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}