Bubble Sort

You are given an array of integers. Your task is to sort the array using the bubble sort algorithm.

The bubble sort algorithm repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each pass through the array, the largest unsorted element is moved to its correct position.

The algorithm can be described using the following formula:

$$\text{for } i = 0 \text{ to } n-1: \quad \text{for } j = 0 \text{ to } n-i-2: \quad if\; a_j > a_{j+1}\; then \; swap(a_j, a_{j+1})$$

Implement the sorting algorithm and print the sorted array as the final output.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the array. The second line contains n integers separated by spaces, representing the array elements.

Example:

5
64 34 25 12 22

outputFormat

Output the sorted array in a single line. The numbers must be separated by a single space.

Example:

12 22 25 34 64

## sample

5
64 34 25 12 22

12 22 25 34 64