Problem Description
Damian’s favourite game is ‘Gravity Guy’. Have you played it before?
Damian has discovered a secret portal in the game and has navigated gravity guy to a secret room full of crates. There are N vertical columns of crates, and there are Ai crates in the ith column from the left. Gravity is in the downward direction initially.
Damian taps gravity guy and gravity changes to the leftward direction. Help Damian find out how many crates there are in each column now!
Input
The first line of input contains a single integer N, the number of columns.
The next N lines contain one integer each, the ith of which is Ai, the number of crates in the ith column.
Output
Output N integers, one on each line. The integer on the ith line should describe the number of crates in the ith column after the change in the direction of gravity.
Limits
Subtask 1 (20%): 1 ≤ N ≤ 1000, 1 ≤ Ai ≤ 1000
Subtask 2 (20%): 1 ≤ N ≤ 1000, 1 ≤ Ai ≤ 109
Subtask 3 (25%): 1 ≤ N ≤ 1 000 000, 1 ≤ Ai ≤ 1 000 000
Subtask 4 (35%): 1 ≤ N ≤ 1 000 000, 1 ≤ Ai ≤ 109
Subtask 5 (0%): Sample Testcases
Sample Testcase 1
Input
6
3
1
4
2
1
2
Output
4
3
2
2
1
1
Explanation
This is the initial configuration of boxes, when gravity was pointing downwards:
After the change in direction of gravity (to leftwards), the configuration of boxes is now:
