Bubble Sort

Problem statement

A classroom robot can exchange only neighboring number cards on its rail. The instructor asks it to repeatedly sweep the rail and swap adjacent cards that are out of order until the displayed sequence is sorted. Your task Sort the array in nondecreasing order using bubble sort: compare adjacent elements during each pass and swap them when the left value is larger. Important details Preserve duplicate cards. Stop early if a pass makes no swaps. Use O(1) auxiliary space; the worst-case running time is O(n squared). Values can be negative and may already be sorted. The output shows the final order rather than the intermediate passes. Worked example For labels 6, -2, 6, 1, the final order is -2, 1, 6, 6. Both copies of 6 remain because sorting changes positions, not the number of records.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

1 <= n <= 2000; -1000000000 <= values <= 1000000000.

Sample input

4
6 -2 6 1

Sample output

-2 1 6 6