class BinaryHeap:
    def __init__(self):
        self.heaplist = [0]
        self.currentsize = 0

    def perceedUp(self,index):
        while index // 2 > 0:
            if self.heaplist[index] < self.heaplist[index // 2]:
                self.heaplist[index // 2], self.heaplist[index] = self.heaplist[index], self.heaplist[index // 2]
            index = index // 2

    def insert(self, item):
        self.heaplist.append(item)
        self.currentsize += 1
        self.perceedUp(self.currentsize)

    def perceedDown(self, index):
        while index * 2 <= self.currentsize:
            minChildIndex = self.minChild(index)
            if self.heaplist[minChildIndex] < self.heaplist[index]:
                self.heaplist[minChildIndex], self.heaplist[index] = self.heaplist[index], self.heaplist[minChildIndex]
                index = minChildIndex
            else:
                break

    def minChild(self, index):
        if index * 2 + 1 > self.currentsize:
            return index * 2
        else:
            if self.heaplist[index * 2] < self.heaplist[index * 2 + 1]:
                return index * 2
            else:
                return index * 2 + 1

    def delMin(self):
        result = self.heaplist[1]
        self.heaplist[1] = self.heaplist[self.currentsize]
        self.currentsize -= 1
        self.heaplist.pop()
        self.perceedDown(1)
        return result

    def buildHeap(self, li):
        i = len(li) // 2
        self.heaplist = [0] + li
        self.currentsize = len(li)
        while i:
            self.perceedDown(i)
            i -= 1