import (
	"container/heap"
)

type MedianFinder struct {
	max MaxHeap  // The left part (smaller part) of data
	min MinHeap  // The right part of data
	odd bool
}

/** initialize your data structure here. */
func Constructor() (mf MedianFinder) {
	return
}

func (this *MedianFinder) AddNum(num int) {
	if this.max.length == 0 || num < this.max.Max() {
		heap.Push(&this.max, num)
		if this.max.length-this.min.length == 2 {
			heap.Push(&this.min, heap.Pop(&this.max))
		}
	} else {
		heap.Push(&this.min, num)
		if this.min.length-this.max.length == 1 {
			heap.Push(&this.max, heap.Pop(&this.min))
		}
	}
	this.odd = !this.odd
}

func (this *MedianFinder) FindMedian() float64 {
	if this.odd {
		return float64(this.max.Max())
	}
	return float64(this.max.Max()+this.min.Min()) / 2.0
}

type MaxHeap struct {
	heap   []int
	length int
}

func (max MaxHeap) Len() int           { return max.length }
func (max MaxHeap) Less(i, j int) bool { return max.heap[i] > max.heap[j] }
func (max MaxHeap) Swap(i, j int)      { max.heap[i], max.heap[j] = max.heap[j], max.heap[i] }

func (max MaxHeap) Max() int {
	return max.heap[0]
}

func (max *MaxHeap) Push(x interface{}) {
	max.heap = append(max.heap, x.(int))
	max.length++
}

func (max *MaxHeap) Pop() interface{} {
	max.length--
	top := max.heap[max.length]
	max.heap = max.heap[:max.length]
	return top
}

type MinHeap struct {
	heap   []int
	length int
}

func (min MinHeap) Len() int           { return min.length }
func (min MinHeap) Less(i, j int) bool { return min.heap[i] < min.heap[j] }
func (min MinHeap) Swap(i, j int)      { min.heap[i], min.heap[j] = min.heap[j], min.heap[i] }

func (min MinHeap) Min() int {
	return min.heap[0]
}

func (min *MinHeap) Push(x interface{}) {
	min.heap = append(min.heap, x.(int))
	min.length++
}

func (min *MinHeap) Pop() interface{} {
	min.length--
	top := min.heap[min.length]
	min.heap = min.heap[:min.length]
	return top
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddNum(num);
 * param_2 := obj.FindMedian();
 */