// Runtime: 79 ms, faster than 84.61% of Java online submissions for Find Median from Data Stream.
// Memory Usage: 66 MB, less than 55.93% of Java online submissions for Find Median from Data Stream.

class MedianFinder {

    /** initialize your data structure here. */
    public MedianFinder() {

    }

    private List<Integer> nums = new ArrayList<>();
    public void addNum(int num) {
        int idx = Collections.binarySearch(nums, num);
        int ip = idx;
        if (idx < 0) {
            ip = -idx - 1;
        }
        nums.add(ip, num);
    }

    public double findMedian() {
        int sizeIdx = nums.size()-1;
        if (nums.size() % 2 == 0) {
            return (nums.get(sizeIdx / 2) + nums.get(sizeIdx / 2 + 1)) / 2.;
        } else {
            return nums.get(sizeIdx / 2);
        }
    }
}