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


def merge(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000001)
    R.append(1000000001)
    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


from array import array
def merge_with_array(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = array('I', A[left:mid])
    R = array('I', A[mid:right])
    L.append(1000000001)
    R.append(1000000001)

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

from ctypes import *
class DATA(Structure):
    _fields_ = ("d", c_int * 250002),
L = DATA()
R = DATA()

def merge_with_ctypes(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L.d[i] = A[left+i]
    for i in range(n2):
        R.d[i] = A[mid+i]
    L.d[n1] = 1000000001
    R.d[n2] = 1000000001

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L.d[i] <= R.d[j]:
            A[k] = L.d[i]
            i += 1
        else:
            A[k] = R.d[j]
            j += 1



Comp_count = 0
if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    S = [int(x) for x in input().split(' ')]
    #with open('ALDS1_5_B_in10.txt') as f:
    #    for line in f:
    #        if ' ' not in line:
    #            num_of_data = int(line)
    #        else:
    #            S = [int(x) for x in line.split(' ')]
    #S = [8, 5, 9, 2, 6, 3, 7, 1, 10, 4]

    # ????????????????????????
    merge_sort(S, 0, num_of_data)

    # ???????????????
    print('{0}'.format(' '.join(map(str, S))))
    print(Comp_count) def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) merge_sort if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) left + 1 < right left + 1 left 1 right mid = (left + right) // 2 mid (left + right) // 2 left + right left right 2 merge_sort(A, left, mid) merge_sort A left mid merge_sort(A, mid, right) merge_sort A mid right merge(A, left, mid, right) merge A left mid right A A left left right right def merge(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000001)
    R.append(1000000001)
    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 merge global Comp_count n1 = mid - left n1 mid - left mid left n2 = right - mid n2 right - mid right mid L = A[left:mid] L A[left:mid] A left:mid left mid R = A[mid:right] R A[mid:right] A mid:right mid right L.append(1000000001) L.append L append 1000000001 R.append(1000000001) R.append R append 1000000001 i = 0 i 0 j = 0 j 0 for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 k range(left, right) range left right Comp_count += 1 Comp_count 1 if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 L[i] <= R[j] L[i] L i R[j] R j A[k] = L[i] A[k] A k L[i] L i i += 1 i 1 A[k] = R[j] A[k] A k R[j] R j j += 1 j 1 A A left left mid mid right right from array import array def merge_with_array(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = array('I', A[left:mid])
    R = array('I', A[mid:right])
    L.append(1000000001)
    R.append(1000000001)

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 merge_with_array global Comp_count n1 = mid - left n1 mid - left mid left n2 = right - mid n2 right - mid right mid L = array('I', A[left:mid]) L array('I', A[left:mid]) array 'I' A[left:mid] A left:mid left mid R = array('I', A[mid:right]) R array('I', A[mid:right]) array 'I' A[mid:right] A mid:right mid right L.append(1000000001) L.append L append 1000000001 R.append(1000000001) R.append R append 1000000001 i = 0 i 0 j = 0 j 0 for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 k range(left, right) range left right Comp_count += 1 Comp_count 1 if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 L[i] <= R[j] L[i] L i R[j] R j A[k] = L[i] A[k] A k L[i] L i i += 1 i 1 A[k] = R[j] A[k] A k R[j] R j j += 1 j 1 A A left left mid mid right right from ctypes import * class DATA(Structure):
    _fields_ = ("d", c_int * 250002), DATA _fields_ = ("d", c_int * 250002), _fields_ ("d", c_int * 250002) "d" c_int * 250002 c_int 250002 Structure L = DATA() L DATA() DATA R = DATA() R DATA() DATA def merge_with_ctypes(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L.d[i] = A[left+i]
    for i in range(n2):
        R.d[i] = A[mid+i]
    L.d[n1] = 1000000001
    R.d[n2] = 1000000001

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L.d[i] <= R.d[j]:
            A[k] = L.d[i]
            i += 1
        else:
            A[k] = R.d[j]
            j += 1 merge_with_ctypes global Comp_count n1 = mid - left n1 mid - left mid left n2 = right - mid n2 right - mid right mid for i in range(n1):
        L.d[i] = A[left+i]
     i range(n1) range n1 L.d[i] = A[left+i] L.d[i] L.d L d i A[left+i] A left+i left i for i in range(n2):
        R.d[i] = A[mid+i]
     i range(n2) range n2 R.d[i] = A[mid+i] R.d[i] R.d R d i A[mid+i] A mid+i mid i L.d[n1] = 1000000001 L.d[n1] L.d L d n1 1000000001 R.d[n2] = 1000000001 R.d[n2] R.d R d n2 1000000001 i = 0 i 0 j = 0 j 0 for k in range(left, right):
        Comp_count += 1
        if L.d[i] <= R.d[j]:
            A[k] = L.d[i]
            i += 1
        else:
            A[k] = R.d[j]
            j += 1 k range(left, right) range left right Comp_count += 1 Comp_count 1 if L.d[i] <= R.d[j]:
            A[k] = L.d[i]
            i += 1
        else:
            A[k] = R.d[j]
            j += 1 L.d[i] <= R.d[j] L.d[i] L.d L d i R.d[j] R.d R d j A[k] = L.d[i] A[k] A k L.d[i] L.d L d i i += 1 i 1 A[k] = R.d[j] A[k] A k R.d[j] R.d R d j j += 1 j 1 A A left left mid mid right right Comp_count = 0 Comp_count 0 if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    S = [int(x) for x in input().split(' ')]
    #with open('ALDS1_5_B_in10.txt') as f:
    #    for line in f:
    #        if ' ' not in line:
    #            num_of_data = int(line)
    #        else:
    #            S = [int(x) for x in line.split(' ')]
    #S = [8, 5, 9, 2, 6, 3, 7, 1, 10, 4]

    # ????????????????????????
    merge_sort(S, 0, num_of_data)

    # ???????????????
    print('{0}'.format(' '.join(map(str, S))))
    print(Comp_count) __name__ == '__main__' __name__ '__main__' num_of_data = int(input()) num_of_data int(input()) int input() input int(x) for x in input().split(' ') for x in input().split(' ') x input().split(' ') ().split () input split ' ' for x in input().split(' ') int(x) int x S = [int(x) for x in input().split(' ')] S [int(x) for x in input().split(' ')] merge_sort(S, 0, num_of_data) merge_sort S 0 num_of_data print('{0}'.format(' '.join(map(str, S)))) print '{0}'.format(' '.join(map(str, S))) '{0}'.format '{0}' format ' '.join(map(str, S)) ' '.join ' ' join map(str, S) map str S print(Comp_count) print Comp_count num_of_data = int(input()) int(input()) num_of_data Comp_count = 0 0 Comp_count S = [int(x) for x in input().split(' ')] [int(x) for x in input().split(' ')] S def merge_with_array(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = array('I', A[left:mid])
    R = array('I', A[mid:right])
    L.append(1000000001)
    R.append(1000000001)

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 def merge_with_array(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = array('I', A[left:mid])
    R = array('I', A[mid:right])
    L.append(1000000001)
    R.append(1000000001)

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 merge_with_array R = DATA() DATA() R def merge(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000001)
    R.append(1000000001)
    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 def merge(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000001)
    R.append(1000000001)
    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1 merge L = DATA() DATA() L class DATA(Structure):
    _fields_ = ("d", c_int * 250002), class DATA(Structure):
    _fields_ = ("d", c_int * 250002), DATA def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) merge_sort def merge_with_ctypes(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L.d[i] = A[left+i]
    for i in range(n2):
        R.d[i] = A[mid+i]
    L.d[n1] = 1000000001
    R.d[n2] = 1000000001

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L.d[i] <= R.d[j]:
            A[k] = L.d[i]
            i += 1
        else:
            A[k] = R.d[j]
            j += 1 def merge_with_ctypes(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L.d[i] = A[left+i]
    for i in range(n2):
        R.d[i] = A[mid+i]
    L.d[n1] = 1000000001
    R.d[n2] = 1000000001

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L.d[i] <= R.d[j]:
            A[k] = L.d[i]
            i += 1
        else:
            A[k] = R.d[j]
            j += 1 merge_with_ctypes
def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def merge(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000001)
    R.append(1000000001)
    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


from array import array
def merge_with_array(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = array('I', A[left:mid])
    R = array('I', A[mid:right])
    L.append(1000000001)
    R.append(1000000001)

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

from ctypes import *
class DATA(Structure):
    _fields_ = ("d", c_int * 250002),
L = DATA()
R = DATA()

def merge_with_ctypes(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L.d[i] = A[left+i]
    for i in range(n2):
        R.d[i] = A[mid+i]
    L.d[n1] = 1000000001
    R.d[n2] = 1000000001

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L.d[i] <= R.d[j]:
            A[k] = L.d[i]
            i += 1
        else:
            A[k] = R.d[j]
            j += 1



Comp_count = 0
if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    S = [int(x) for x in input().split(' ')]
    #with open('ALDS1_5_B_in10.txt') as f:
    #    for line in f:
    #        if ' ' not in line:
    #            num_of_data = int(line)
    #        else:
    #            S = [int(x) for x in line.split(' ')]
    #S = [8, 5, 9, 2, 6, 3, 7, 1, 10, 4]

    # ????????????????????????
    merge_sort(S, 0, num_of_data)

    # ???????????????
    print('{0}'.format(' '.join(map(str, S))))
    print(Comp_count)