牛牛正在学习数据结构，并且对中位数特别感兴趣。他希望你能帮助他实现一个中位数查找器的类。该类需要支持两个操作：添加整数和查找中位数。 具体要求如下： 实现一个名为MedianFinder的类，并在初始化时创建一个空的数据结构。 实现一个名为addNum的方法，用于将数据流中的整数添加到数据结构中。 实现一个名为findMedian的方法，返回到目前为止所有元素的中位数。如果元素个数为偶数，则返回中间两个元素的平均值。 注意： 返回的中位数答案与实际答案相差在10^-5以内将被接受。 在调用findMedian方法之前，数据结构中至少有一个元素。 最多进行5 * 10^4次调用addNum和findMedian方法。 请你实现MedianFinder类，并编写一个函数validateTestCase来验证输入的测试用例。

备注:

input：一个二维整数数组，表示调用MedianFinder类的操作序列。每个操作是一个长度为2的数组，第一个元素表示操作类型（0表示初始化，1表示添加整数，2表示查找中位数），第二个元素表示操作所需的参数。