사라진 난쟁이
면접 대비시간 제한2초메모리 제한512 MB
1부터 n까지의 순열 중 주어진 부분 수열을 포함하는 사전순으로 가장 앞선 순열을 구한다.
문제
난쟁이 n명이 단체 사진을 찍으려고 줄을 선다. 각 난쟁이는 모자에 적힌 1..n 사이의 번호로 구별된다.
난쟁이가 5명이라고 하자. 난쟁이들은 1, 3, 4, 2, 5처럼 줄을 설 수 있다.
이제 사악한 마법사가 줄에서 난쟁이 몇 명을 데려가고, 너의 기억에서 난쟁이들의 순서를 지운다. 남는 것은 부분 수열이며, 예를 들어 1, 4, 2가 될 수 있다.
그런 다음 마법사는 1..n의 모든 순열을 사전순으로 나열했을 때, 남은 부분 수열을 포함하는 첫 번째 순열이 원래 난쟁이들의 순서라고 알려 준다. 원래 난쟁이들의 순서를 구하라.
입력
각 입력은 하나의 테스트 케이스로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다. 각 테스트 케이스의 첫 줄에는 두 정수 n과 m (1 ≤ m ≤ n ≤ 105)이 주어진다. n은 처음에 있던 난쟁이의 수이고, m은 사악한 마법사의 장난 이후에 남은 난쟁이의 수이다. 다음 m개 줄에는 각각 하나의 정수 g (1 ≤ g ≤ n)가 주어진다. 이는 남아 있는 난쟁이들을 순서대로 나타낸다. g의 값은 모두 서로 다르다.
출력
n개 줄에 걸쳐 정수를 하나씩 출력한다. 이는 남아 있는 난쟁이들을 순서대로 포함할 수 있는 첫 번째 순열을 나타낸다.