Construct Sorted Array

You are given an integer n and an array A of n integers. Your task is to construct an array B such that when B is sorted in non-decreasing order, for each index i (1-indexed) the number of elements in A that are less than or equal to B_i is exactly i.

In mathematical terms, for each i (1 ≤ i ≤ n), the following condition should hold:

$$\#\{x \in A: x \leq B_i\} = i.$$

It turns out that sorting the array A always produces an array B satisfying this condition. If for some reason a valid array can not be constructed, you should output Impossible. (Note: under the problem constraints, a solution always exists.)

Example:

• Input: n = 5, A = [3, 1, 4, 1, 5]
• Output: B = [1, 1, 3, 4, 5]

inputFormat

The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers representing the array A.

outputFormat

If a valid array B can be constructed, output the elements of B in one line separated by spaces. Otherwise, output Impossible.

5
3 1 4 1 5

1 1 3 4 5