Let's reformulate the problem.

The median of an array A is the floor(n / 2)-th element of sort(A).

You have an array B and you must find the median element for every prefix of B.

The solution to this problem:

Create a sorted doubly-linked list of all elements of A, and for each element of A keep the pointer to the corresponding node in the list. This step can be done in O(NlogN).

We now want to track the k-largest element using a pointer, let's call that pointer "middle". Initially just find the floor(n / 2)-th element in the list. For the median problem, the value of k changes but that's not a big issue as we're about to see.

Starting from the end of A, remove elements one by one from the list. Each time you remove a number from the list, adjust the pointer accordingly — if the number removed was before the "middle" you need to move "middle" to the next node in the list. Otherwise do not move "middle".

Now, when the value of k decreases, for example, this happens when we used to have 8 elements and after removing one we have 7, the value of k changes from 4 to 3 and again we need to adjust "middle". It's simple — when k decreases just move "middle" to the previous node of the list.

To solve the main problem just apply the above algorithm to every suffix of A. Note that you can obtain the N sorted linked lists for every suffix of A in O(n²) time.

Hope this was clear enough :)