import copy

def partition(a, fro, to):
    if fro >= to:
        return fro
    # Hoare partitioning scheme
    mid = (fro+to) // 2
    piv = a[mid]
    lo, hi = fro-1, to+1
    while True:
        lo += 1
        while a[lo] < piv:
            lo += 1
        hi -= 1
        while a[hi] > piv:
            hi -= 1
        if lo >= hi:
            return hi
        a[lo], a[hi] = a[hi], a[lo]

def quicksort(a, fro=0, to=-1):
    if to < 0:
        to = len(a) - 1
    if to-fro <= 0:
        return
    mid = partition(a, fro, to)
    quicksort(a, fro, mid)
    quicksort(a, mid+1, to)

def mergehalves(a, lo, mid, hi, aux):
    i, l, r = 0, lo, mid
    while i <= hi-lo:
        if l >= mid:
            aux[i] = a[r]
            r += 1
        elif r > hi:
            aux[i] = a[l]
            l += 1
        else:
            if a[l] < a[r]:
                aux[i] = a[l]
                l += 1
            else:
                aux[i] = a[r]
                r += 1
        i += 1
    a[lo:hi+1] = aux[0:i]

def mergesort(a, lo=0, hi=-1, aux=None):
    aux = aux or copy.copy(a)
    hi = hi if hi > 0 else len(a)-1
    if hi == lo:
        return
    elif hi-lo == 1:
        if a[lo] > a[hi]:
            a[lo], a[hi] = a[hi], a[lo]
        return
    else:
        mid = (lo+hi)//2
        mergesort(a, lo, mid, aux)
        mergesort(a, mid, hi, aux)
        mergehalves(a, lo, mid, hi, aux)

def children(i):
    return (2*i, 2*i+1)

def swap(a, i, j):
    a[i], a[j] = a[j], a[i]


def sink(a, i, N=-1):
    N = N if N >= 0 else len(a)
    while 2*i < N:
        c1, c2 = children(i)
        if c2 >= N:
            if a[i] < a[c1]:
                swap(a, i, c1)
            i = c1
        else:
            sm, la = (c1, c2) if a[c1] < a[c2] else (c2, c1)
            if a[i] < a[la]:
                swap(a, i, la)
            i = la

def buildheap(a):
    i = len(a) // 2
    while i > 0:
        sink(a, i)
        i -= 1

def heapsort(a):
    a = [0] + a
    buildheap(a)
    i = len(a)-1
    while i > 0:
        swap(a, 1, i)
        i -= 1
        sink(a, 1, i)

    return a