class RunningMedian {

    public double getMedian() {
        if (upperHalf.isEmpty() && lowerHalf.isEmpty()) {
            throw new RuntimeException("Add values before getting the median");
        }

        if (upperHalf.size() > lowerHalf.size()) {
            return upperHalf.peek();
        } else if (lowerHalf.size() > upperHalf.size()) {
            return lowerHalf.peek();
        } else {
            return 0.5 * (lowerHalf.peek() + upperHalf.peek());
        }
    }

}