Given a list of n numbers, the median is the number of rank dn/2e, i. e., it is the dn/2eth smallest element. Suppose the list is changing dynamically. That is at every step, a number is added or deleted from the list. The goal is to output the median in the current list as fast as possible. In other words, at any point in time, we would like to answer the query: "What is the median of the current list of numbers ?". How fast can you answer this query?