Warehouse Pallet Insertion Line

A warehouse dock receives pallets one at a time, in a fixed arrival order. Each pallet carries an integer priority tag (duplicates are possible, and tags may be negative). As each pallet arrives, warehouse workers place it directly onto a single-file storage line: they may only walk forward along the line from its entrance, one pallet at a time, so a new pallet is always slotted into the line at the point that keeps the whole line sorted by priority tag from smallest (nearest the entrance) to largest, before the next pallet is allowed to arrive.

Given the pallets in their arrival order, determine the priority tags of the final storage line, from the entrance outward, after every pallet has been placed.

Input format

Line 1: one integer n, the number of pallets. Line 2 (present only when n > 0): n integers, the pallets' priority tags in arrival order.

Output format

A single line containing the n priority tags of the final storage line, from the entrance outward, in non-decreasing order, separated by single spaces (an empty line if n = 0).

Constraints

• 0 <= n <= 5000
• Each priority tag is an integer with -5000 <= tag <= 5000

5
4 2 1 3 5

1 2 3 4 5

6
3 -1 3 0 -1 2

-1 -1 0 2 3 3