Suppose Alice guesses some value x in {0, ..., n^2}, and she wants to determine whether x < Median(A), x = Median(A), or x > Median(A). How can Alice and Bob answer this question by sending two messages of O(lg n) bits each? Now you have a comparison subroutine that takes 2 messages. So just use binary search.