Question $2.(20$ marks$)$ We want to compute the median of every prefix of an input array A$[1..$n$]$ of arbitrary integers. More precisely, design an algorithm that outputs another array M $[1..$n$],$ so that M $[$i$]$ is equal to the median of the integers in the subarray A$[1..$i$].$ Recall that when i is odd, the median of A$[1..$i$]$ is the element of rank $($i $+1)/2$ in the subarray, and when i is even, the median is the average of the elements with ranks i$/2$ and i$/2+1.$ Your algorithm should run in worst$-$case time O$($n log n$).$ Hint: Maintain two heaps for the subarray A$[1..$i$]$: one that contains $$i$/2$ elements of this subarray, and one that contains $$i$/2$ elements of this subarray. What elements of A$[1..$i$]$ should each one of these heaps contain? What kind of heap each one them is$?$ How do you use them to compute the median of A$[1..$i$]?$ How do you maintain these heaps when you increase i to i $+1?$ a$.$ Describe your algorithm in clear and concise English, and also provide the corresponding pseudocode. Argue that your algorithm is correct. b$.$ Justify why your algorithm runs in time O$($n log n$)$ in the worst case.