def merge_sort(a):

    return _merge_sort(a)



def _merge_sort(a):

    if len(a) == 1:

        return a,0

    m = len(a)/2

    b,count1 = _merge_sort(a[0:m])

    c,count2 = _merge_sort(a[m:len(a)])

    ret,count3 = merge(b,c)

    return (ret,count1+count2+count3)



def merge(b,c):

    a = []

    i = 0

    j = 0

    count = 0

    while i < len(b) and j < len(c):

        count += 1

        if b[i] > c[j]:

            a.append(c[j])

            j += 1

        else:

            a.append(b[i])

            i += 1

    if i == len(b):

        while j < len(c):

            count += 1

            a.append(c[j])

            j += 1

    elif j == len(c):

        while i < len(b):

            count += 1

            a.append(b[i])

            i += 1

    return a,count



n = int(input())

a = list(map(int,input().split(' ')))

ret,count = merge_sort(a)

print(' '.join(map(str,ret)))

print(count)
global_count = 0



def sort(a):

    return merge_sort(a)



def merge_sort(a):

    n = len(a)

    if n <= 1:

        return a

    lo = 0

    hi = n

    med = (lo+hi)/2

    left = merge_sort(a[lo:med])

    right = merge_sort(a[med:hi])

    return merge(left, right)



def merge(a,b):

    global global_count

    c = []

    na = len(a)

    nb = len(b)

    i = 0

    j = 0

    while i < na and j < nb:

        if a[i] < b[j]:

            global_count += 1

            c.append(a[i])

            i += 1

        else:

            global_count += 1

            c.append(b[j])

            j += 1



    if i == na:

        while j < nb:

            global_count += 1

            c.append(b[j])

            j += 1

    if j == nb:

        while i < na:

            global_count += 1

            c.append(a[i])

            i += 1



    return c



n = int(input())

a = list(map(int, input().split(' ')))

c = sort(a)

print(' '.join(map(str, c)))

print(global_count)
def merge_sort(a):
    return _merge_sort(a)


def _merge_sort(a):
    if len(a) == 1:
        return a, 0
    m = len(a) / 2
    b, count1 = _merge_sort(a[0:m])
    c, count2 = _merge_sort(a[m : len(a)])
    ret, count3 = merge(b, c)
    return (ret, count1 + count2 + count3)


def merge(b, c):
    a = []
    i = 0
    j = 0
    count = 0
    while i < len(b) and j < len(c):
        count += 1
        if b[i] > c[j]:
            a.append(c[j])
            j += 1
        else:
            a.append(b[i])
            i += 1
    if i == len(b):
        while j < len(c):
            count += 1
            a.append(c[j])
            j += 1
    elif j == len(c):
        while i < len(b):
            count += 1
            a.append(b[i])
            i += 1
    return a, count


n = int(input())
a = list(map(int, input().split(" ")))
ret, count = merge_sort(a)
print(" ".join(map(str, ret)))
print(count)

global_count = 0


def sort(a):
    return merge_sort(a)


def merge_sort(a):
    n = len(a)
    if n <= 1:
        return a
    lo = 0
    hi = n
    med = (lo + hi) / 2
    left = merge_sort(a[lo:med])
    right = merge_sort(a[med:hi])
    return merge(left, right)


def merge(a, b):
    global global_count
    c = []
    na = len(a)
    nb = len(b)
    i = 0
    j = 0
    while i < na and j < nb:
        if a[i] < b[j]:
            global_count += 1
            c.append(a[i])
            i += 1
        else:
            global_count += 1
            c.append(b[j])
            j += 1
    if i == na:
        while j < nb:
            global_count += 1
            c.append(b[j])
            j += 1
    if j == nb:
        while i < na:
            global_count += 1
            c.append(a[i])
            i += 1
    return c


n = int(input())
a = list(map(int, input().split(" ")))
c = sort(a)
print(" ".join(map(str, c)))
print(global_count)

-def merge_sort(a): -    return _merge_sort(a) +global_count = 0 -def _merge_sort(a): -    if len(a) == 1: -        return a, 0 -    m = len(a) / 2 -    b, count1 = _merge_sort(a[0:m]) -    c, count2 = _merge_sort(a[m : len(a)]) -    ret, count3 = merge(b, c) -    return (ret, count1 + count2 + count3) +def sort(a): +    return merge_sort(a) -def merge(b, c): -    a = [] +def merge_sort(a): +    n = len(a) +    if n <= 1: +        return a +    lo = 0 +    hi = n +    med = (lo + hi) / 2 +    left = merge_sort(a[lo:med]) +    right = merge_sort(a[med:hi]) +    return merge(left, right) + + +def merge(a, b): +    global global_count +    c = [] +    na = len(a) +    nb = len(b) -    count = 0 -    while i < len(b) and j < len(c): -        count += 1 -        if b[i] > c[j]: -            a.append(c[j]) +    while i < na and j < nb: +        if a[i] < b[j]: +            global_count += 1 +            c.append(a[i]) +            i += 1 +        else: +            global_count += 1 +            c.append(b[j]) -        else: -            a.append(b[i]) +    if i == na: +        while j < nb: +            global_count += 1 +            c.append(b[j]) +            j += 1 +    if j == nb: +        while i < na: +            global_count += 1 +            c.append(a[i]) -    if i == len(b): -        while j < len(c): -            count += 1 -            a.append(c[j]) -            j += 1 -    elif j == len(c): -        while i < len(b): -            count += 1 -            a.append(b[i]) -            i += 1 -    return a, count +    return c -ret, count = merge_sort(a) -print(" ".join(map(str, ret))) -print(count) +c = sort(a) +print(" ".join(map(str, c))) +print(global_count)