def sort(a):
    span = 0
    work = 0
    while True:
        eswaps = 0
        for i in range(0, len(a)-1, 2):
            if a[i] > a[i+1]:
                eswaps += 1
                a[i], a[i+1] = a[i+1], a[i]
        if eswaps > 0:
            span += 1
            work += eswaps
        oswaps = 0
        for i in range(1, len(a)-1, 2):
            if a[i] > a[i+1]:
                oswaps += 1
                a[i], a[i+1] = a[i+1], a[i]
        if oswaps > 0:
            span += 1
            work += oswaps
        if eswaps + oswaps == 0:
            return span, work

def permutations(n):
    #returns a list of the permutations of [0,...,n-1]
    if n == 0:
        return [[]]
    shorterOnes = permutations(n-1)
    results = []
    # add in all the variants of the shorter ones
    for p in shorterOnes:
        for i in range(n):
            # calculate variant number i of shorter permutation p
            theVariant = p[:i] + [n-1] + p[i:]
            results.append(theVariant)
    return results