None def swap def sift_up while if break else swap def add append sift

H = [None]

def swap(a, b):
    H[a], H[b] = H[b], H[a]

def sift_up(v):
    while v != 1:
        if H[v // 2] > H[v]:
            break
        else:
            swap(v // 2, v)
            v = v // 2

def add(x):
    H.append(x)
    sift_up(len(H) - 1)

def sift_down(v):
    while 2 * v < len(H):
        ind = 2 * v
        if 2 * v + 1 < len(H) and H[2 * v + 1] > H[2 * v]:
            ind = 2 * v + 1
        if H[ind] < H[v]:
            break
        swap(v, ind)
        v = ind

def extract_min():
    swap(1, len(H) - 1)
    ret = H.pop()
    sift_down(1)
    return ret