"""练习 11 进阶版：保留三种排序算法，去掉逐行教学注释。"""
def bubble_sort(data):
    values = data[:]
    comparisons = 0
    for end in range(len(values) - 1, 0, -1):
        swapped = False
        for index in range(end):
            comparisons += 1
            if values[index] > values[index + 1]:
                values[index], values[index + 1] = values[index + 1], values[index]
                swapped = True
        if not swapped:
            break
    return values, comparisons


def selection_sort(data):
    values = data[:]
    comparisons = 0
    for start in range(len(values) - 1):
        minimum = min(range(start, len(values)), key=values.__getitem__)
        comparisons += len(values) - start - 1
        values[start], values[minimum] = values[minimum], values[start]
    return values, comparisons


def insertion_sort(data):
    values = data[:]
    comparisons = 0
    for index in range(1, len(values)):
        key = values[index]
        position = index - 1
        while position >= 0:
            comparisons += 1
            if values[position] <= key:
                break
            values[position + 1] = values[position]
            position -= 1
        values[position + 1] = key
    return values, comparisons


n = int(input())
values = list(map(int, input().split()))[:n]
for name, sort_function in (("bubble", bubble_sort), ("selection", selection_sort), ("insertion", insertion_sort)):
    result, comparisons = sort_function(values)
    print(name + ":", *result)
    print("comparisons:", comparisons)