A. Minimizing Inversions with a Predetermined Prefix
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You, as the great master of numbers, have been entrusted with an extremely important task, upon which, according to ancient prophecies, depends not only the fate of the contest scoreboard, but perhaps the entire computational universe. $$$ \\ $$$ In a certain kingdom of integers, there lives a noble set $$$S = \{1, 2, 3, \cdots, n\}$$$, where there are no repeated elements—each inhabitant is unique. However, recently, strange events have begun to occur in this set. $$$ \\ $$$ The great oracle, using the magical powers of foresight, has predetermined exactly how the first $$$m$$$ numbers of the final permutation will be arranged. These elements are already firmly fixed in their positions at the beginning of the future array—and they cannot be moved, for they are sealed by the will of fate. $$$ \\ $$$ Your task, O mighty arranger, is as follows: determine the order of the remaining $$$n-m$$$ elements $$$(p_{m+1}, p_{m+2}, \cdots, p_n)$$$ so that, after combining them with the predetermined prefix, the resulting permutation $$$p = [p_1, p_2, p_3, \cdots, p_n]$$$ is still valid (that is, contains all numbers from $$$1$$$ to $$$n$$$ exactly once), and at the same time, the number of inversions in it is as small as possible. $$$ \\ $$$ Definitions:

  • A permutation of length $$$n$$$ is an array of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$, where each number appears exactly once.
  • An inversion in a permutation is a pair of indices $$$(i, j)$$$ such that $$$(1 \le i \lt j \le n)$$$ and at the same time $$$(p_i \gt p_j)$$$.
Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le m \lt n \le 10^{5})$$$—the total number of elements and the number of fixed numbers, respectively. $$$ \\ $$$ The second line contains $$$m$$$ distinct integers: $$$p_1, p_2, \cdots, p_m$$$, each of which belongs to the range from $$$1$$$ to $$$n$$$, and all are distinct.

Output

Print $$$n-m$$$ integers—elements $$$p_{m+1}, p_{m+2}, \cdots, p_n$$$—such that the result $$$p = [p_1, p_2, p_3, \cdots, p_n]$$$ is a valid permutation, and the number of inversions in it is as small as possible.

Examples
Input
10 7
5 1 2 9 3 4 6
Output
7 8 10
Input
5 4
1 2 3 4
Output
5