A space elevator hauls cargo to orbit using a chain of coupler-linked pods that runs from a base platform up to a summit dock. Each pod carries a fixed mass (which may be negative, since some pods carry buoyant ballast instead of cargo), and for the chain to stay structurally stable during ascent, the pods must be linked so mass never decreases as you go up the chain. Ground control needs the resulting chain order, from base to summit, after the pods are relinked so their masses are non-decreasing.

Input format

• Line 1: a single integer n (0 ≤ n ≤ 50000), the number of pods currently coupled in the chain, listed base-to-summit.
• Line 2: n space-separated integers m_1 m_2 ... m_n (-100000 ≤ m_i ≤ 100000), the mass of each pod in its current base-to-summit order. If n = 0 this line is empty.

Output format

Print the masses of the pods, space-separated on one line, after relinking the chain so masses are non-decreasing from base to summit. If n = 0, print an empty line.

Constraints

• 0 ≤ n ≤ 50000
• -100000 ≤ m_i ≤ 100000
• Masses may repeat.

4
9 3 5 3

3 3 5 9

5
-2 8 0 -5 8

-5 -2 0 8 8