If \(A\) contains either \(1\) or \(N\), a good permutation does not exist.

Conversely, if neither \(1\) nor \(N\) is included in \(A\), a good permutation does exist. Let’s consider this case.

For example, if we set \(P = (1, N, N - 1, N - 2, \dots, 3, 2)\), the only contiguous subsequence of \(P\) that includes both \(1\) and \(2\) is \(P\) itself, making \(P\) a good permutation.

Since a good permutation with \(P_{1} = 1\) exists, the lexicographically smallest good permutation will have \(P_{1} = 1\). In this case, for any integer \(x\), if there exists a contiguous subsequence of \(P\) that is a permutation of \((1, 2, \dots, x)\), it must be \((P_{1}, P_{2}, \dots, P_{x})\).

We determine \(P_{i}\) for \(i \neq 1\) in ascending order of \(i\). When deciding \(P_{i}\), we assume that all of \(P_{1}, P_{2}, \dots, P_{i - 1}\) are at most \(i\). Let \(a\) be the number that is at most \(i\) and not included in \(P_{1}, P_{2}, \dots, P_{i - 1}\).

When \(i\) is included in \(A\)

To make the permutation lexicographically smallest, we set \(P_{i} = i + 1\), because if we set \(P_{i} = a\), it would not be a good permutation. Since \(P_{i}\) is not greater than \(i + 1\), all of \(P_{1}, P_{2}, \dots, P_{i}\) will be at most \(i + 1\), and \(a\) does not change.

When \(i\) is not included in \(A\)

To make the permutation lexicographically smallest, we set \(P_{i} = a\). Since this number is not greater than \(i\), all of \(P_{1}, P_{2}, \dots, P_{i}\) will be at most \(i + 1\), and \(a\) becomes \(i + 1\).

Therefore, we can implement this to solve the problem. The time complexity is \(O(N)\).

# input
N, M = map(int, input().split())
A = list(map(int, input().split()))
ban = [0] * N
for a in A:
    # 1-index  -> 0-index
    ban[a - 1] = 1;

# impossible
if ban[0] or ban[N - 1]:
    print(-1)
    quit()

# init
P = [0] * N
P[0] = 1
a = 2

# calc
for i in range(1, N):
    if ban[i] == 1:
        P[i] = i + 2
    else:
        P[i] = a
        a = i + 2

# output
print(*P)

Additionally, you can also construct the permutation as follows:

Initialize \(P = (1, 2, \dots, N)\), and for \(i = 2, 3, \dots, N - 1\), perform the following operation:

• If \(i\) is included in \(A\), do \(\text{swap}(P_{i}, P_{i + 1})\).

Implementation example in C++