#coding:utf-8

#1_5_B

def merge_sort(array):

    if len(array) > 1:

        L, countL = merge_sort(array[0:len(array)//2])

        R, countR = merge_sort(array[len(array)//2:])

        return merge(L, R, countL+countR)



    if len(array) == 1:

        return [array, 0]



def merge(L, R, count=0):

    L.append(10**9+1)

    R.append(10**9+1)

    response = []

    i = 0

    j = 0

    for k in range(len(L)-1 + len(R)-1):

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

            response.append(L[i])

            i += 1

            count += 1

        else:

            response.append(R[j])

            j += 1

            count += 1

    return [response, count]



n = int(eval(input()))

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

numbers, count = merge_sort(S)

print((*numbers))

print(count)
#coding:utf-8

#1_5_B

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

    global cnt

    n1 = mid - left

    n2 = right - mid

    L = array[left:mid]  + [sentinel]

    R = array[mid:right] + [sentinel]

    i = j = 0

    for k in range(left, right):

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

            array[k] = L[i]

            i += 1

        else:

            array[k] = R[j]

            j += 1

    cnt += right - left



def merge_sort(array, left, right):

    if left + 1 < right:

        mid = (left + right) // 2

        merge_sort(array, left, mid)

        merge_sort(array, mid, right)

        merge(array, left, mid, right)





n = int(eval(input()))

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

cnt = 0

sentinel = 10 ** 9 + 1

merge_sort(S, 0, len(S))

print((*S))

print(cnt)
# coding:utf-8
# 1_5_B
def merge_sort(array):
    if len(array) > 1:
        L, countL = merge_sort(array[0 : len(array) // 2])
        R, countR = merge_sort(array[len(array) // 2 :])
        return merge(L, R, countL + countR)
    if len(array) == 1:
        return [array, 0]


def merge(L, R, count=0):
    L.append(10**9 + 1)
    R.append(10**9 + 1)
    response = []
    i = 0
    j = 0
    for k in range(len(L) - 1 + len(R) - 1):
        if L[i] <= R[j]:
            response.append(L[i])
            i += 1
            count += 1
        else:
            response.append(R[j])
            j += 1
            count += 1
    return [response, count]


n = int(eval(input()))
S = list(map(int, input().split()))
numbers, count = merge_sort(S)
print((*numbers))
print(count)

# coding:utf-8
# 1_5_B
def merge(array, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = array[left:mid] + [sentinel]
    R = array[mid:right] + [sentinel]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1
    cnt += right - left


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


n = int(eval(input()))
S = list(map(int, input().split()))
cnt = 0
sentinel = 10**9 + 1
merge_sort(S, 0, len(S))
print((*S))
print(cnt)

-def merge_sort(array): -    if len(array) > 1: -        L, countL = merge_sort(array[0 : len(array) // 2]) -        R, countR = merge_sort(array[len(array) // 2 :]) -        return merge(L, R, countL + countR) -    if len(array) == 1: -        return [array, 0] +def merge(array, left, mid, right): +    global cnt +    n1 = mid - left +    n2 = right - mid +    L = array[left:mid] + [sentinel] +    R = array[mid:right] + [sentinel] +    i = j = 0 +    for k in range(left, right): +        if L[i] <= R[j]: +            array[k] = L[i] +            i += 1 +        else: +            array[k] = R[j] +            j += 1 +    cnt += right - left -def merge(L, R, count=0): -    L.append(10**9 + 1) -    R.append(10**9 + 1) -    response = [] -    i = 0 -    j = 0 -    for k in range(len(L) - 1 + len(R) - 1): -        if L[i] <= R[j]: -            response.append(L[i]) -            i += 1 -            count += 1 -        else: -            response.append(R[j]) -            j += 1 -            count += 1 -    return [response, count] +def merge_sort(array, left, right): +    if left + 1 < right: +        mid = (left + right) // 2 +        merge_sort(array, left, mid) +        merge_sort(array, mid, right) +        merge(array, left, mid, right) -numbers, count = merge_sort(S) -print((*numbers)) -print(count) +cnt = 0 +sentinel = 10**9 + 1 +merge_sort(S, 0, len(S)) +print((*S)) +print(cnt)