Bubble Sort Algorithm

Given an array of integers, your task is to implement the bubble sort algorithm which sorts the array in non-decreasing order. The bubble sort algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until no more swaps are needed. The algorithm can be described mathematically as follows:

$$\text{For } i=0 \text{ to } n-1:\newline \quad \text{For } j=0 \text{ to } n-i-2:\newline \quad \quad \text{if } a[j] > a[j+1], \text{ swap } a[j] \text{ and } a[j+1].$$

The time complexity of bubble sort in the worst-case scenario is $O(n^2)$.

inputFormat

The first line contains an integer $n$, indicating the number of elements in the array. The second line contains $n$ space-separated integers.

outputFormat

Output the sorted array as a single line with the numbers separated by a single space.

## sample

5
1 2 3 4 5

1 2 3 4 5

</p>