Write a program of the Bubble Sort algorithm which sorts a sequence _A_ in ascending order. The algorithm should be based on the following pseudocode:                 BubbleSort(A) 1 for i = 0 to A.length-1 2     for j = A.length-1 downto i+1 3         if A[j] < A[j-1] 4             swap A[j] and A[j-1]   Note that, indices for array elements are based on 0-origin.  Your program should also print the number of swap operations defined in line 4 of the pseudocode.
def bubble_sort(array):
    flag = True
    while flag:
        flag = False
        for i in range(N-1, 0, -1):
            if array[i] < array[i-1]:
                array[i], array[i-1] = array[i-1], array[i]
                flag = True

def merge_count(array):
    if len(array) <= 1:
        return array, 0
    mid = len(array) // 2
    left, cl = merge_count(array[:mid])
    right, cr = merge_count(array[mid:])
    count = cl + cr
    left = list(reversed(left))
    right = list(reversed(right))
    for i in range(len(array)):
        if not left:
            array[i] = right.pop()
        elif not right:
            array[i] = left.pop()
        elif left[-1] <= right[-1]:
            array[i] = left.pop()
        else:
            array[i] = right.pop()
            count += len(left)
    return array, count

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(merge_count(A)[1])
def bubble_sort(array):
    flag = True
    while flag:
        flag = False
        for i in range(N-1, 0, -1):
            if array[i] < array[i-1]:
                array[i], array[i-1] = array[i-1], array[i]
                flag = True

def merge_count(array):
    if len(array) <= 1:
        return array, 0
    mid = len(array) // 2
    left, cl = merge_count(array[:mid])
    right, cr = merge_count(array[mid:])
    count = cl + cr
    left = list(reversed(left))
    right = list(reversed(right))
    for i in range(len(array)):
        if not left:
            array[i] = right.pop()
        elif not right:
            array[i] = left.pop()
        elif left[-1] <= right[-1]:
            array[i] = left.pop()
        else:
            array[i] = right.pop()
            count += len(left)
    return array, count

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    a, b = merge_count(A)
    print(*a)
    print(b)