This question is from Facebook recruiting portal.

Hi all,
I have a phone screen at facebook and they gave a list of problems for practise.
I dont get how to go about this one:

You're given a list of n integers arr[0..(n-1)]. You must compute a list output[0..(n-1)] such that, for each index i (between 0 and n-1, inclusive), output[i] is equal to the median of the elements arr[0..i] (rounded down to the nearest integer).
The median of a list of integers is defined as follows. If the integers were to be sorted, then:
- If there are an odd number of integers, then the median is equal to the middle integer in the sorted order.
- Otherwise, if there are an even number of integers, then the median is equal to the average of the two middle-most integers in the sorted order.

Example 1:

n = 4
arr = [5, 15, 1, 3]
output = [5, 10, 5, 4]
The median of [5] is 5, the median of [5, 15] is (5 + 15) / 2 = 10, the median of [5, 15, 1] is 5, and the median of [5, 10, 1, 3] is (3 + 5) / 2 = 4.