\(\color{blue}{Tade}\) là một thủ thư làm việc rất chuyên cần ở thư viện \(Abcdef\). Hôm nay, \(\color{blue}{Tade}\) được \(Big Boss\) giao nhiệm vụ sắp xếp lại đống sách mới được gửi đến. Khổ nỗi, \(Boss\) lại yêu cầu \(\color{blue}{Tade}\) sắp xếp \(10^7\) đống sách theo thứ tự không giảm trong vòng \(1s\), mà trong thời gian đó anh ta chỉ có thể sắp xếp được \(10^6\) quyển thôi.

\(\color{blue}{Tade}\) đành phải nhờ đến các bạn lqdcoder giúp đỡ, các bạn hãy giúp anh ấy nhé!

Input

• Dòng đầu chứa một số tự nhiên \(N (1\le N\le 10^7)\) là số sách mà Tade cần phải sắp xếp.

• Dòng tiếp theo chứa \(N\) số tự nhiên \(a_i (1\le a_i\le 100)\), là số thứ tự của mỗi quyển sách. Lưu ý, hai quyển sách có thể có cùng một số thứ tự.

Output

• Một dòng chứa \(N\) số là các số thứ tự được sắp xếp không giảm của \(N\) quyển sách đó.

Example

6
1 5 4 2 3 4

1 2 3 4 4 5