Problem of the day
The first line of input contains an integer 'N', denoting the number of integers in the stream.
The second line of input contains 'N' integers separated by a single space.
Print the running median for every integer added to the running list in one line (space-separated).
0 <= N <= 10 ^ 5
1 <= ARR[i] <= 10 ^ 5
Time Limit: 1 sec
6
6 2 1 3 7 5
6 4 2 2 3 4
S = {6}, median = 6
S = {6, 2} -> {2, 6}, median = 4
S = {6, 2, 1} -> {1, 2, 6}, median = 2
S = {6, 2, 1, 3} -> {1, 2, 3, 6}, median = 2
S = {6, 2, 1, 3, 7} -> {1, 2, 3, 6, 7}, median = 3
S = {6, 2, 1, 3, 7, 5} -> {1, 2, 3, 5, 6, 7}, median = 4
5
5 4 3 2 1
5 4 4 3 3