\(A\) に \(1\) もしくは \(N\) が含まれているときは良い順列は存在しません。

逆に \(A\) に \(1\) と \(N\) がどちらも含まれていないときは良い順列が存在します。このときを考えます。

例えば \(P = (1 ,N, N - 1, N - 2, \dots, 3, 2)\) とすると、\(1, 2\) どちらも含む \(P\) の連続部分列は \(P\) 自身しか存在しないため、\(P\) は良い順列となります。

以上のように \(P_{1} = 1\) となる良い順列が存在するため、辞書順最小の良い順列は \(P_{1} = 1\) となります。このとき、任意の整数 \(x\) に対して、\(P\) の連続部分列で \((1, 2, \dots , x)\) の順列であるものが存在するなら \((P_{1}, P_{2}, \dots , P_{x})\) に限ります。

\(i=1\) を除く \(P_{i}\) を \(i\) の小さい順に決めていきます。ここで、\(P_{i}\) を決めるときに、\(P_{1},P_{2},\dots P_{i - 1}\) は全て \(i\) 以下の数であることを満たしているとします。また、\(P_{1}, P_{2}, \dots P_{i - 1}\) に含まれていない \(i\) 以下の数を \(a\) とします。

\(A\) に \(i\) が含まれているとき

辞書順最小にするために、\(P_{i} = a\) とすると、良い順列でなくなるため、\(P_{i}=i+1\) とします。\(P_{i}\) は \(i+1\) 以下であるため、\(P_{1}, P_{2}, \dots P_{i}\) は全て \(i+1\) 以下の数になります。また、\(a\) は変化しません。

\(A\) に \(i\) が含まれていないとき

辞書順最小にするため、\(P_{i} = a\) とします。この数は \(i\) 以下の数であるため、\(P_{1}, P_{2}, \dots P_{i}\) は全て \(i+1\) 以下の数になります。また、\(a\) は \(i+1\) になります。

よって、以上を実装すれば良いです。計算量は \(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)

また、以下のようにしても構築できます。

\(P = (1, 2, \dots ,N)\) と初期化した後、 \(i = 2, 3, \dots ,N - 1\) の順に、以下の操作をする。

• \(A\) に \(i\) が含まれているなら、\(\text{swap}(P_{i},P_{i + 1})\) をする。

c++ による実装例