LeetCode 295 Find Median from Data Stream - Why Naive Fails

Keep a sorted list. On each addNum, insert in the right position. For findMedian, return the middle element(s).

Insertion into a sorted array takes $O(n)$ to shift elements. With $n$ insertions, total is $O(n^2)$.

Can you add numbers faster while still finding the median quickly?