Cho dãy ~n~ số nguyên ~A = \{a_1, a_2,\ldots, a_n\}~. Để sắp thứ tự tăng dần của các phần tử của dãy số trên Thuận tìm được rất nhiều thuật toán sắp có thể làm được công việc đó, bao gồm:

• Thuật toán sắp xếp nổi bọt (https://en.wikipedia.org/wiki/Bubble_sort).

• Thuật toán sắp xếp chèn (https://en.wikipedia.org/wiki/Insertion_sort).

• Thuật toán sắp xếp chọn (https://en.wikipedia.org/wiki/Selection_sort).

• Thuật toán sắp xếp trộn (https://en.wikipedia.org/wiki/Merge_sort).

Và vô số thuật toán sắp xếp khác. Thuận cố gắng cài từng thuật toán một trong các thuật toán kể trên nhưng vẫn chưa accept được. Các bạn hãy lập trình giúp Thuận.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~1 \le n \le 5000~.

Dòng tiếp theo chứa các ~n~ số nguyên ~a_i~ thỏa ~|a_i| \le 10^6~.

Output

In dãy được sắp theo thứ tự tăng dần.

Samples

Sample Input 1

5
3 1 2 -9 12

Sample Output 1

-9 1 2 3 12

Note

Các bạn phải cài đặt từng thuật toán theo yêu cầu để học hỏi và thử nghiệm các thuật toán sắp xếp.