|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Training #7Ended |
D - Missing Gnomes
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
A family of $n$ gnomes likes to line up for a group picture. Each gnome can be uniquely identified by a number $1..n$ written on their hat.
Suppose there are $5$ gnomes. The gnomes could line up like so: $1, 3, 4, 2, 5$.
Now, an evil magician will remove some of the gnomes from the lineup and wipe your memory of the order of the gnomes. The result is a subsequence, perhaps like so: $1, 4, 2$.
He then tells you that if you ordered all permutations of $1..n$ in lexicographical order, the original sequence of gnomes is the first such permutation which contains the remaining subsequence. Your task is to find the original sequence of gnomes.
Input
Each input will consist of a single test case. Note that your program may be run multiple times on
different inputs. Each test case will begin with a line with two integers $n$ and then $m$ $(1 \leq m \leq n \leq 10^5)$, where $n$ is the number of gnomes originally, and $m$ is the number of gnomes remaining
after the evil magician pulls his trick. Each of the next $m$ lines will contain a single integer $g$ $(1 \leq g \leq n)$. These are the remaining gnomes, in order. The values of $g$ are guaranteed to be
unique.
Output
Output $n$ lines, each containing a single integer, representing the first permutation of gnomes that
could contain the remaining gnomes in order.
Sample test(s)
Input
5 3
1
4
2
Output
1
3
4
2
5
Input
7 4
6
4
2
1
Output
3
5
6
4
2
1
7