You are given a stream of 'N' integers. For every 'i-th' integer added to the running list of integers, print the resulting median.
Print only the integer part of the median.
Input Format :
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.
Output Format :
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
The median of n numbers is the middle-most element among the numbers when sorted in ascending order, when n is odd, and is the average of the two middle-most elements, when n is even. To find the middle-most elements, we do this: For every new addition to the stream, we sort all the numbers that are currently present. This makes it easy for us to obtain the middle-most elements.