SENTINEL = 2000000000

L = R = [0]

cnt = 0

def merge(A, n, left, mid, right):

    L = A[left:mid] + [SENTINEL]

    R = A[mid:right] + [SENTINEL]

    i = j = 0

    global cnt

    for k in range(left, right):

        cnt += 1

        if L[i] <= R[j]:

            A[k] = L[i]

            i += 1

        else:

            A[k] = R[j]

            j += 1

def mergeSort(A, n, left, right):

    if left + 1 < right:

        mid = (left + right) // 2

        mergeSort(A, n, left, mid)

        mergeSort(A, n, mid, right)

        merge(A, n, left, mid, right)

n = int(eval(input()))

A = [int(i) for i in input().split()]

mergeSort(A, n, 0, n)

print((*A))

print(cnt)
INF = float("inf")

cnt = 0

def merge(A, left, mid, right):

    global cnt

    n1 = mid - left

    n2 = right - mid

    L = A[left: left + n1] + [INF]

    R = A[mid: mid + n2] + [INF]

    i = j = 0

    for k in range(left, right):

        cnt += 1

        if L[i] <= R[j]:

            A[k] = L[i]

            i += 1

        else:

            A[k] = R[j]

            j += 1

def mergeSort(A, left, right):

    if left + 1 < right:

        mid = (left + right) // 2

        mergeSort(A, left, mid)

        mergeSort(A, mid, right)

        merge(A, left, mid, right)

n = int(eval(input()))

S = list(map(int, input().split()))

mergeSort(S, 0, n)

print((*S))

print(cnt)



SENTINEL = 2000000000
L = R = [0]
cnt = 0


def merge(A, n, left, mid, right):
    L = A[left:mid] + [SENTINEL]
    R = A[mid:right] + [SENTINEL]
    i = j = 0
    global cnt
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def mergeSort(A, n, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, n, left, mid)
        mergeSort(A, n, mid, right)
        merge(A, n, left, mid, right)


n = int(eval(input()))
A = [int(i) for i in input().split()]
mergeSort(A, n, 0, n)
print((*A))
print(cnt)

INF = float("inf")
cnt = 0


def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left : left + n1] + [INF]
    R = A[mid : mid + n2] + [INF]
    i = j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)


n = int(eval(input()))
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print((*S))
print(cnt)

-SENTINEL = 2000000000 -L = R = [0] +INF = float("inf") -def merge(A, n, left, mid, right): -    L = A[left:mid] + [SENTINEL] -    R = A[mid:right] + [SENTINEL] +def merge(A, left, mid, right): +    global cnt +    n1 = mid - left +    n2 = right - mid +    L = A[left : left + n1] + [INF] +    R = A[mid : mid + n2] + [INF] -    global cnt -def mergeSort(A, n, left, right): +def mergeSort(A, left, right): -        mergeSort(A, n, left, mid) -        mergeSort(A, n, mid, right) -        merge(A, n, left, mid, right) +        mergeSort(A, left, mid) +        mergeSort(A, mid, right) +        merge(A, left, mid, right) -A = [int(i) for i in input().split()] -mergeSort(A, n, 0, n) -print((*A)) +S = list(map(int, input().split())) +mergeSort(S, 0, n) +print((*S))