class MedianFinder {
    TreeMap<Integer, Integer> map;
    int median;
    int lowerCount;
    int higherCount;

    /** initialize your data structure here. */
    public MedianFinder() {
        map = new TreeMap<Integer, Integer>();
    }

    public void addNum(int num) {
        Integer count = map.get(num);
        if (count == null) count = 0;
        count++;
        map.put(num, count);

        if (map.size() > 1) {
            if (num > median) higherCount++;
            else if (num < median) lowerCount--;

            int medianCount = map.get(median);
            System.out.println(num + " median=" + median + " medianCount=" + medianCount + " l=" + lowerCount + " h=" + higherCount);

            if (higherCount > lowerCount + medianCount) {
                System.out.println("going higher");
                median = map.higherKey(median);
                lowerCount += medianCount;
                higherCount -= map.get(median);
            } else if (lowerCount < medianCount + higherCount - 2) {
                System.out.println("going lower");
                median = map.lowerKey(median);
                lowerCount -= map.get(median);
                higherCount += medianCount;
            }

            System.out.println("after median=" + median + " medianCount=" + medianCount + " l=" + lowerCount + " h=" + higherCount);
        } else {
            median = num;
            lowerCount = 0;
            higherCount = 0;
        }
    }

    public double findMedian() {
        if (higherCount > lowerCount) return (median + map.higherKey(median))/2;
        if (lowerCount < higherCount) return (median + map.lowerKey(median))/2;
        return median;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */